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

遍历写法"/>

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

蓝桥杯 全球变暖（dfs)

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

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

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

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

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

输出
一个整数表示答案。

样例输入

样例输出
1

OJ链接

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

AC代码：

#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;
}