本文主要是介绍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;
}
这篇关于2018 蓝桥杯 全球变暖(dfs) 深度优先遍历写法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!