连通块用广搜

//题目:全球变暖(AcWing)
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int vis[1005][1005][3];
string str[1005];
int xx[]={0,1,0,-1};
int yy[]={1,0,-1,0};
struct L{
int x,y;
};
void bfs(int x,int y){
queue<l>q;
q.push( (L){x,y} );
vis[x][y][1]=1;
int cnt1=1,cnt2=0; //cnt1:构成这座岛屿的陆地的数量 //cnt2:这座岛屿中陆地被淹没的数量
while(!q.empty()){
int f=0;
for(int i=0;i<4;++i){
int dx=q.front().x+xx[i];
int dy=q.front().y+yy[i];
if(dx>=0&&dx<n&&dy>=0&&dy<n&&str[dx][dy]=='.'&&!vis[q.front().x][q.front().y][2]){
vis[q.front().x][q.front().y][2]=1;
cnt2++;
}
if(dx>=0&&dx<n&&dy>=0&&dy<n&&str[dx][dy]=='#'&&!vis[dx][dy][1]){
q.push( (L){dx,dy} );
vis[dx][dy][1]=1;
cnt1++;
}
}
q.pop();
}
if(cnt1==cnt2) ans++;
}
int main(){
cin >> n;
for(int i=0;i<n;++i){
cin >> str[i];
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(str[i][j]=='#'&&!vis[i][j][1]) bfs(i,j); //对这块陆地所在的岛屿(即连通块)进行操作
}
}
cout << ans;
return 0;
}</l>

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务