第九届蓝桥杯b组—全球变暖（C语言）

题目描述：

.......
.##....
.##....
....##.
..####.
...###.
.......

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

.......
.......
.......
.......
....#..
.......
.......

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

样例：

7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出：

1

思路：

这题我用dfs来解决。可以对'#'周围四个方向判断，如果是‘.’则代表会被淹没，对于岛屿被淹没个数，我们可以用count代表每个岛屿被淹掉几块地，用total代表一块岛屿搜索到的“#”的数量，当两者相等时代表这块岛屿完全淹没。

 完整代码：

#include
int ans,n,a[101][101],st[101][101],count,total;
char ch;
int next[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void dfs(int x,int y)
{st[x][y]=1;//标记走过 total++;//岛屿数 for(int i=0;i<4;i++)//四个方向测试，看看会淹没多少 {int tx=x+next[i][0];int ty=y+next[i][1];if(a[tx][ty]==1){count++;//记录每个岛屿淹掉几块地 break;}}for(int i=0;i<4;i++)//四个方向进行搜索 {int tx=x+next[i][0];int ty=y+next[i][1];if(tx<1||tx>n||ty<1||ty>n) continue;if(a[tx][ty]==0&&!st[tx][ty])// 此地是岛屿且此块地没有走过 {dfs(tx,ty);}}
}
int main()
{scanf("%d",&n); for(int i=1;i<=n;i++){getchar();//吸收回车 for(int j=1;j<=n;j++){scanf("%c",&ch);if(ch=='.') a[i][j]=1;if(ch=='#') {a[i][j]=0;}}	}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(a[i][j]==0&&!st[i][j]){total=count=0;//搜索每个岛屿前要将计数器初始化 dfs(i,j);if(total==count) ans++;//如果这块岛屿全部淹没两者值应该相同	 }}printf("%d",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！