2018 蓝桥杯 全球变暖(dfs) 深度优先遍历写法

发表于 分类于 阅读次数： 本文字数： 761 阅读时长 ≈ 3 分钟

这是2018年蓝桥杯C语言省赛B组的第九题

题目
你有一张某海域NxN像素的照片，”.”表示海洋、”#”表示陆地，如下所示：
1

其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。
具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
1

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。

输出
一个整数表示答案。

样例输入
1
样例输出
1

OJ链接

思路：在接收初始图之后，首先搜索查找初始岛屿数，在找到一个岛屿后，对整个岛屿进行标记，防止重复计数。随后再次进行搜索，如果有四周均为陆地的坐标，则标记此坐标未被淹没。最后查找所有未被淹没的坐标，并将坐标所处的整个岛标记，防止重复计数。初始岛屿数量减去未被淹没岛的数量，即为被淹没的岛的数量。

AC代码：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;

char maps[1001][1001];

void dfs1(int x,int y)
{
	if(maps[x][y]!='#')
		return;
	maps[x][y]='1';//将#标记为1 
	dfs1(x+1,y);//把整个岛都进行标记 防止重复计算 
	dfs1(x-1,y);
	dfs1(x,y+1);
	dfs1(x,y-1);
} 

void dfs2(int x,int y)
{
	if(maps[x][y]=='.')
		return;
	if(maps[x+1][y]=='1'&&maps[x-1][y]=='1'&&maps[x][y+1]=='1'&&maps[x][y-1]=='1')//四周都是陆地 则标记为2
	{	
		maps[x][y]='2'; 
	} 
	dfs1(x+1,y);//找4个方向 
	dfs1(x-1,y);
	dfs1(x,y+1);
	dfs1(x,y-1);
} 

void dfs3(int x,int y)
{
	if(maps[x][y]=='.')
		return;
	maps[x][y]='.';//将#标记为 . 
	dfs3(x+1,y);//把整个岛都进行沉没操作 防止重复计算 
	dfs3(x-1,y);
	dfs3(x,y+1);
	dfs3(x,y-1);
} 

int main()
{
	int n,first_num=0,end_num=0;//层数 初始岛屿数量 末尾岛屿数量 
	scanf("%d",&n); 
	for(int a=1;a<=n;a++)
	{
		for(int b=1;b<=n;b++)
		{
			while(1)
			{
				scanf("%c",&maps[a][b]);
				if(maps[a][b]=='.'||maps[a][b]=='#')
					break;
			}
		}
	}
	//先查找有多少个岛屿 
	for(int a=1;a<=n;a++)
	{
		for(int b=1;b<=n;b++)
		{
			if(maps[a][b]=='#')
			{
				dfs1(a,b);
				first_num++;//初始岛屿+1 
			}
		}
	}
	//再对整个岛屿进行变化
	for(int a=1;a<=n;a++)
	{
		for(int b=1;b<=n;b++)
		{
			if(maps[a][b]=='1')
			{
				dfs2(a,b);
			}
		}
	}
	//最后查找剩余多少个岛屿 
	for(int a=1;a<=n;a++)
	{
		for(int b=1;b<=n;b++)
		{
			if(maps[a][b]=='2')
			{
				dfs3(a,b);
				end_num++;//最终岛屿+1 
			}
		}
	}
	
	cout<<first_num-end_num;
	return 0;
}