acwing1233. 全球变暖

题目

题解

记录边界数和总节点数，若两者相等，则说明该岛会被淹没。

#include<iostream>
using namespace std;
const int N=1010;
typedef pair<int,int> PII;
#define x first 
#define y second
PII q[N*N];
char g[N][N];
bool st[N][N];
int n;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void bfs(int x,int y,int &total,int &bound){
    int hh=0,tt=0;
    q[hh]={x,y};
    st[x][y]=true;
    while(hh<=tt){
        auto t=q[hh++];
        st[t.x][t.y]=true;
        total++;
        bool is_bound=false;
        for(int i=0;i<4;i++){
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<0||a>=n||b<0||b>=n)continue;
            if(st[a][b])continue;
            if(g[a][b]=='.'){
               is_bound=true;
               continue;
            }
            q[++tt]={a,b};
            st[a][b]=true;
        }
        if(is_bound)bound++;
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>g[i];
    int cnt=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!st[i][j]&&g[i][j]=='#'){
                int total=0,bound=0;
                bfs(i,j,total,bound);
                if(total==bound)cnt++;
            }
        }
    }
    cout<<cnt<<endl;
    
    return 0;
}