洛谷P7645 ARHIPELAG

传送门

题目背景

一个受欢迎的旅游目的地国家坐落在一个惊人美丽的群岛上沐浴在阳光下。这个国家的居民以其众多的岛屿为傲。然而,全球气候变暖让他们非常担心:海平面上升导致干燥土地的流失迅速增加，这削弱了群岛的美丽。

题目描述

这个群岛的地图是一个 RR 行 CC 列的方阵。X 表示陆地，. 表示海。据估计，在 5050 年里，海水将淹没目前所有三面或四面环海的土地。

假设地图外全被海覆盖。你的任务是计算出 5050 年后的群岛地图(在所描述的海平面上升之后)。

因为那时的土地可能会比今天更少，你不需要打印出整个地图，而只是包含所有的土地的最小的矩形部分。

输入格式

第一行包含两个整数 RR 和 CC，表示地图有 RR 列 CC 行；

第 22 至 R+1R+1 行，目前群岛的地图，X 表示陆地，. 表示海。

输出格式
一个矩阵，表示 5050 年后群岛的地图。

输入输出样例

输入 #1复制
5 3
…
.X.
.X.
.X.
…
输出 #1复制
X
输入 #2复制
3 10
…
…XXX.XXX.
XXX…
输出 #2复制
.XX…X
XX…

说明/提示

【数据范围】

对于 100%100% 的数据，1\le R,C \le 101≤R,C≤10。

【说明】

本题分值按 COCI 原题设置，满分 8080。

题目译自 COCI2012~2013 CONTEST #5 T2 ARHIPELAG。

上代码：

#include//万能头文件 
using namespace std;
bool flag[15][15],f[15][15];//第一个flag用来判断岛屿和大海，第二个f记录是否淹没 
const int d[5]={1,0,-1,0,1};//上下左右四个方位 
int main(){
	int n,m;
	cin >> n >> m;//输入长，宽 
	for(int i=1;i<=n;i++){//为了后面运算防止超出范围，i和j要从1开始 
		for(int j=1;j<=m;j++){
			char t;
			cin >> t;
			if(t=='.')flag[i][j]=0;//判断岛屿海洋 
			else flag[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int tem=0;//计数器，存贮周围海洋的个数 
			if(flag[i][j]==1){
				for(int k=0;k<4;k++){//四个方位枚举 
					int x=i,y=j;
					x+=d[k];
					y+=d[k+1];
					if(flag[x][y]==0) tem++;
					
				}
			}
			if(tem>=3)f[i][j]=1;//这里不能写成下面那样，需要一个f来记录这里会不会被海水淹没 
			// 如果写成下面那样，在第一行做运算的时候，会把岛屿变成海洋
			//导致第二次运算错误
			// if(tem>=3)flag[i][j]=0;  <-千万不要这么写 
		}
	}
	int u=99,d=1,l=99,r=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(f[i][j]==1)flag[i][j]=0;
			if(flag[i][j]==1){
				u=min(u,i);//判断最上侧 
				l=min(l,j);//判断最左侧
				d=max(d,i);//判断最下侧
				r=max(r,j);//判断最右侧
			}
			
		}
	}
	if(u==99){//如果没有岛屿，全部输出"."； 
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cout << '.';
			}
			cout << endl;
		}
	}
	for(int i=u;i<=d;i++){
		for(int j=l;j<=r;j++){
			if(flag[i][j]==0) cout << '.';//输出 
			else cout << "X" ;
		}
		cout << endl;//不要忘记每一行换行 
	}
	
	
	return 0;//华丽的结束 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65