AcWing 1233. 全球变暖
原题链接
简单
作者:
Lyle2021
,
2021-01-21 20:24:50
,
所有人可见
,
阅读 256
(BFS)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N =1010;
char g[N][N];
int n;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
bool check(int sx,int sy){
for(int i=0;i<4;i++){
int a=sx+dx[i],b=sy+dy[i];
if(g[a][b]=='.'){
return true;
break;
}
}
return false;
}
bool bfs(int sx,int sy){
bool flag=true;
if(sx>=1&&sx<n-1&&sy>=1&&sy<n-1&&!check(sx,sy)){
g[sx][sy]='@';
flag=false;
return flag;
}
g[sx][sy]='@';
queue<PII> q;
q.push({sx,sy});
while(q.size()){
auto t =q.front();
q.pop();
for(int i=0;i<4;i++){
int a=t.x+dx[i],b=t.y+dy[i];
if(a<1||a>=n-1||b<1||b>=n-1||g[a][b]=='.'||g[a][b]=='@')continue;
if(g[a][b]=='#'&&check(a,b)){
g[a][b]='@';
q.push({a,b});
}
else if(g[a][b]=='#'&&!check(a,b)){
g[a][b]='@';
q.push({a,b});
flag=false;
}
}
}
return flag;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>g[i];
}
int ans=0;
for(int i=1;i<n-1;i++)
for(int j=1;j<n-1;j++)
if(g[i][j]=='#'){
if(bfs(i,j))ans++;
}
cout<<ans<<endl;
return 0;
}