题目描述
你有一张某海域NxN像素的照片，"."表示海洋、"#"表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。
【样例输入】
7
.......
.##....
.##....
....##.
..####.
...###.
.......
【样例输出】
1
解题思路：
bfs：
对于#：vis[][]=0，表示未访问，vis[][]=1，表示已访问且该位置是临海的，vis[][]=2表示已访问且该位置不临海
对于#,都初始化其vis[][]=2,如果后续它符合临海的条件，再令vis[][]=1
第一次bfs确定vis数组，统计有多少个岛屿，然后把vis[][]=1的位置换成. 表示淹没
第二次bfs统计淹没后还剩余多少岛屿
做差即结果
dfs：
对于#，判断其四周是否都是#，如果是的话不临海#计数器ans++，标志flag为true，一个岛屿中只需要知道有一个不临海的#就可以了，flag避免了重复计算同一个岛屿中不临海#的数量，造成结果错误。
dfs的同时，res_ans统计有多少岛屿
做差即结果
ac代码：
bfs
#include <iostream>
#include <cmath>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#define maxn 1002
using namespace std;
typedef long long ll;
struct node{
int x,y;
node(int x=-1,int y=-1):x(x),y(y){}
};
int vis[maxn][maxn]={0};
char a[maxn][maxn];
int n,ans=0;
queue<node> q;
int X[4]={0,-1,0,1};//x
int Y[4]={1,0,-1,0};//y 右，上，左，下
bool check(int x,int y)
{
for(int i=0;i<4;i++)
{
int c=x+X[i],r=y+Y[i];
if(c>=0&&c<n&&r>=0&&r<n&&a[c][r]=='.')
return true;
}
return false;
}
void bfs()
{
while(!q.empty())
{
node s=q.front();q.pop();
if(check(s.x,s.y))
vis[s.x][s.y]=1;//四个方位有方位临水
for(int i=0;i<4;i++)
{
int c=s.x+X[i],r=s.y+Y[i];
if(c>=0&&c<n&&r>=0&&r<n&&a[c][r]=='#'&&vis[c][r]==0)//不越界且是#且不是已经访问过的
{
vis[c][r]=2;//先把当前#四周的#的vis都设为2，此后满足check（）则vis变成1，否则还是2
q.push(node(c,r));
}
}
}
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%s",a[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(a[i][j]=='#'&&vis[i][j]==0)
{
q.push(node(i,j));
ans++;
bfs();
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(vis[i][j]==1&&a[i][j]=='#')
a[i][j]='.';
}
}
int sum=0;//求最后还剩下多少岛屿
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(a[i][j]=='#'&&vis[i][j]==0)
{
q.push(node(i,j));
sum++;
bfs();
}
}
}
printf("%d",ans-sum);
return 0;
}
dfs：来源大佬https://blog.csdn.net/memeda1141
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
using namespace std;
bool flag;//标记是否岛屿沉没
char a[1010][1010];//地图保存
int cnt=0;//统计周围#的数目
int n;//
int d[4][2]= {1,0,-1,0,0,1,0,-1};//枚举方向的数组
int ans=0;//被淹没后的岛屿个数
int res_ans=0;//没被淹没的岛屿的个数
void dfs(int x,int y)//回溯
{
if(a[x][y]!='#')//如果这个点被标记成已经探索的岛屿内容或者是海洋，那么就返回
return ;
if(x>=n||x<0||y>=n||y<0)//如果越界了也是返回
return ;
if(flag==false)//如果还没确定不会被淹没，即当前是被淹没状态
{cnt=0;//统计这个岛屿的当前点坐标x，y的上下左右的四个点是不是都是'#'，如果确实是这样的，那么为我们就可以确定这个岛屿不会被淹没，我们姑且叫这样的点叫做不可淹没点，，那么只要一个岛屿有一个这样的点就一定不会被淹没
for(int i=0; i<4; i++)//枚举四个方向
{
int tx=x+d[i][0];
int ty=y+d[i][1];
if(tx<n&&tx>=0&&ty<n&&ty>=0&&a[tx][ty]!='.')//假设枚举的四周的点不会超界并且不是海洋，那么cnt数目+1
{
cnt++;
}
}
if(cnt==4)//如果四周的点都是这样的那么这个点就是不可淹没点
{
ans++;//最后不会被淹没的点+！
flag=true;//这个岛屿标记已经确定，当前岛屿是不可以被淹没的，所以当回溯这个岛屿其他点的时候就不用再来检查了，因为一个岛屿有一个这样的不可淹没点就够了
}
}
a[x][y]='*';//对于已经探索的岛屿的内容标记成'*'，
for(int i=0; i<4; i++)
{
int tx=x+d[i][0];
int ty=y+d[i][1];
dfs(tx,ty);//对于四个方向进行回溯岛屿的所有点
}
}
int main()
{
cin>>n;
for(int i=0; i<n; i++)
{
scanf("%s",a[i]);
}//输入数据
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{//遍历地图的所以坐标
if(a[i][j]=='#')//如果被找到的是同一个岛屿那么会被标记成'*',不会进入回溯，只有是'#'才说明是未被搜索的岛屿的一角
{
res_ans++;//那么岛屿数目加1
flag=false;//假设会淹没
dfs(i,j);//回溯标记这个岛屿的所有点的坐标，并且如果不会被完全的淹没，那么就标记
}
}
}
cout<<res_ans-ans<<endl;//输出答案
}
京公网安备 11010502036488号