你有一张某海域NxN像素的照片，".“表示海洋、”#"表示陆地，如下所示：
…
.##…
.##…
…##.
…####.
…###.
…
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
…
…
…
…
…#…
…
…
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案
思路：这道题我们其实就是去用dfs去遍历这个数组 遇到上下左右四个方向都为陆地的就说明这在涨潮后还会是陆地 用一个数组记录 涨潮后还会是陆地的坐标 然后就转化成了一个求几块陆地的问题 成了一道dfs板子题
#include<iostream>
using namespace std;
char map[1005][1005];
char vis[1005][1005];
char dd[1005][1005]; //定义了三个数组 vis是判断陆地四周是否为海 始终不变
int x[4] = {1,0,0,-1}; //map是来记录涨潮之后剩下的陆地 有可能一个陆地变成了两个陆地
int y[4] = {0,1,-1,0}; //dd数组用来是dfs函数里面循环可以正常进行
int m;
bool judge(int a,int b)
{
int ans=0;
for(int i = 0 ; i < 4 ; i++)
{
int nx = a+x[i];
int ny = b+y[i];
if(vis[nx][ny]=='#') ans++;
}
if(ans==4) return true;
else return false;
}
void dfs(int a,int b)
{
for(int i = 0 ; i < 4 ; i++)
{
int nx = a+x[i];
int ny = b+y[i];
if(nx >=0 && nx<=m && ny>=0 && ny <= m && dd[nx][ny]=='#')
{
dd[nx][ny]='.';
if(!judge(nx,ny))
{
map[nx][ny]='.';
dfs(nx,ny);
}
}
}
}
void dfss(int a,int b)
{
for(int i = 0 ; i < 4 ; i++)
{
int nx = a+x[i];
int ny = b+y[i];
if(nx >=0 && nx<=m && ny>=0 && ny <= m && map[nx][ny]=='#')
{
map[nx][ny]='.';
}
}
}
int main()
{
cin >> m;
for(int i=0 ; i <m ; i++)
{
cin >> map[i];
for(int j = 0 ; j < m ; j++)
{
vis[i][j]=map[i][j]; //得到标记数组
dd[i][j]=map[i][j];
}
}
int flag=0;
for(int i = 0 ; i < m ; i++)
{
for(int j = 0 ; j < m ; j++)
{
if(dd[i][j] == '#')
{
dfs(i,j);
}
}
}
for(int i = 0 ; i < m ; i++)
{
for(int j = 0 ; j < m ; j++）
{
if(map[i][j]=='#')
{
dfss(i,j);
flag++;
}
}
}
cout << flag << endl;
return 0;
}
/*这个代码让我很开心 代码二十分钟一遍过 没有任何bug 样例也都通过
虽然题很简单 但真的让一个小白在被codeforces摧残了以后有了一点信心 嘤嘤嘤 */
蓝桥杯的题目都相对比较单一 没有什么坑点 唯一需要注意的是一个陆地在涨潮后有可能成为多块陆地