全球变暖题解

先用BFS对每一个岛进行遍历（代码中BFS_id函数），并为它们标上他们的编号，顺便记录下有几个岛屿。利用queue 将每个是海的地方进行蔓延（代码中BFS_water函数）。最后，在主函数中遍历一遍共有几个id不同的岛屿，与最开始的岛屿数量相减。

#include<bits/stdc++.h>
using namespace std;

char mp[1005][1005];
bool vis[1005][1005];
int id[1005][1005];
int t[1000006];
int sum=0,n;
int fix_X[4]={0,0,1,-1};
int fix_Y[4]={1,-1,0,0};

struct vals{
    int x,y;
};

void bfs_id(int x,int y){//id标记
    sum++;
    vis[x][y]=true;
    id[x][y]=sum;
    queue<vals >q;
    q.push({x,y});
    while(!q.empty()){
        vals f=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int tx=f.x+fix_X[i];
            int ty=f.y+fix_Y[i];
            if(tx>=1 && ty>=1 && tx<=n && ty<=n && mp[tx][ty]=='#' && !vis[tx][ty]){
                q.push({tx,ty});
                vis[tx][ty]=true;
                id[tx][ty]=sum;
            }
        }
    }
    return ;
}

void bfs_water(int x,int y){//水的蔓延
    for(int i=0;i<4;i++){
        int tx=x+fix_X[i];
        int ty=y+fix_Y[i];
        if(tx>=1 && ty>=1 && tx<=n && ty<=n && mp[tx][ty]=='#'){
            id[tx][ty]=0;
        }
    }
    return ;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>mp[i][j];
        }
    }
    for(int i=1;i<=n;i++){//id标记（查找岛屿）
        for(int j=1;j<=n;j++){
            if(mp[i][j]=='#' && !vis[i][j]){
                bfs_id(i,j);
            }
        }
    }
    for(int i=1;i<=n;i++){//海水蔓延
        for(int j=1;j<=n;j++){
            if(mp[i][j]=='.'){
                bfs_water(i,j);
            }
        }
    }
    int sum2=0;
    for(int i=1;i<=n;i++){//统计水蔓延后还有几个id不同的岛屿
        for(int j=1;j<=n;j++){
            if(!t[id[i][j]] && id[i][j]!=0){
                t[id[i][j]]=true;
                sum2++;
            }
        }
    }
    int ans=sum-sum2;
    cout<<ans<<endl;
    return 0;
}