AcWing 1233. 全球变暖---BFS-C++
原题链接
简单
作者:
LeeDV
,
2024-04-10 19:45:52
,
所有人可见
,
阅读 2
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
typedef pair<int,int> PII;
int n;
PII q[N*N];
char g[N][N];
bool st[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool bfs(int sx,int sy)
{
int tt=0,hh=0;
q[0]={sx,sy};
st[sx][sy]=true;
int ret=0;
int cnt=0;
while(hh<=tt)
{
auto e=q[hh++];
int nx=e.first,ny=e.second;
cnt++;//记录联通块内所有
int num=0;
for(int i=0;i<4;i++)
{
int x=nx+dx[i],y=ny+dy[i];
if(x<0||x>=n||y<0||y>=n)continue;
if(g[x][y]=='.'){
num++;
continue;
}
if(st[x][y])continue;
q[++tt]={x,y};
st[x][y]=true;
}
if(num>0)ret++;//记录沉没的小地
}
// cout<<"cnt: "<<cnt<<endl;
// cout<<"ret: "<<ret<<endl;
if(cnt==ret)return true;
else return false;
}
int main()
{
ios:: sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cin>>g[i][j];
}
// for(int i=0;i<n;i++)
// {
// for(int j=0;j<n;j++)
// {cout<<g[i][j];}
// cout<<endl;
// }
int cnt=0;
int all=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(g[i][j]=='#'&&!st[i][j])
{
if( bfs(i,j))// true--沉没连通块++
{
cnt++;
}
}
}
}
// int tmp=all-cnt;
cout<<cnt<<endl;
return 0;
}