全球变暖-dfs问题
作者:
因为yxc爱上编程
,
2024-04-11 21:04:03
,
所有人可见
,
阅读 50
//就是连通块问题,思路要打开灵活一些,需要什么就去判断实现什么,
//首先是要找出连通块的数量,然后再找到那些没有四周都是陆地的岛屿
//求连通块的时候做一个标记即可,标记这个岛屿是否全部被淹没,也就是看是否能找到一个点
//周围全部是陆地
#include<iostream>
using namespace std;
const int N=1010;
int n;
char M [N][N];
int sum=0;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
bool st[N][N];
int flag;//标记岛屿是否被完全淹没
void dfs(int x,int y){
if(M[x][y+1]=='#'&&M[x][y-1]=='#'&&M[x+1][y]=='#'&&M[x-1][y]=='#')
flag=1; //就这样上下左右判断一下,不一定非要用i循环来判断上下左右,思路要打开
//灵活一些
for(int i=0;i<4;i++){
int ax=x+dx[i];
int bx=y+dy[i];
if(ax<0||ax>=n||bx<0||bx>=n||st[ax][bx])continue;
if(M[ax][bx]=='.') continue;
st[ax][bx]=true;
dfs(ax,bx);
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>M[i][j];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(M[i][j]=='#'&&!st[i][j]){
flag=0;//统计一个岛屿就要初始化一下flag
st[i][j]=true;
dfs(i,j);
if(flag==0) sum++;
}
cout<<sum<<endl;
return 0;
}