AcWing 1233. 全球变暖
原题链接
简单
作者:
geats兔
,
2024-03-30 02:37:20
,
所有人可见
,
阅读 1
#include<iostream>
using namespace std;
const int N=1010;
#define x first
#define y second
typedef pair<int,int>PII;
char s[N][N];
int n,count;
bool st[N][N];
PII q[N*N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool bfs(PII start){
int hh=0,tt=0;int sum=1,cnt=0;
q[0]=start;
st[start.x][start.y]=true;
while(hh<=tt){
PII t=q[hh++];
bool flag=false;
for(int i=0;i<4;i++){
int x=t.x+dx[i];int y=t.y+dy[i];
if(x<0||x>=n||y<0||y>=n) continue;
if(st[x][y]) continue;
if(s[x][y]=='.'){
flag=true;
continue;
}
q[++tt]={x,y};
st[x][y]=true;
sum++;
}
if(flag) cnt++;
}
return cnt==sum;
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>s[i];
//int res=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(s[i][j]=='#'&&!st[i][j]) {
PII start={i,j};
if(bfs(start)) count++;
}
}
cout<<count<<endl;
return 0;
}