1233. 全球变暖

https://www.acwing.com/problem/content/1115/
第一步,首先要考虑有多少个连通块,可以直接枚举每个点,对每个点进行一次搜索,与这个点连通的点共同构成一个连通块,数量用cnt表示,在搜索中,检查判断是否会被完全淹没(Flood Fill)

#include<bits/stdc++.h>
using namespace std;
int n;
char a[1010][1010];
int vis[1010][1010]={0};
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
int flag;  //用于标记这个岛中是否被完全淹没
void dfs(int x, int y){
    vis[x][y] = 1;
    if(a[x][y+1]=='#' && a[x][y-1]=='#' && a[x+1][y]=='#' && a[x-1][y]=='#')//此连通块存在不可淹没的地方
        flag = 1;
    for(int i = 0; i < 4; i++)//继续搜索周围的陆地(拓展连通块)
    { 
        int nx = x + d[i][0], ny = y + d[i][1];
        if(vis[nx][ny]==0 && a[nx][ny]=='#')
            dfs(nx,ny);
    }
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)cin >> a[i];
    int ans = 0 ;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(a[i][j]=='#' && vis[i][j]==0){
                flag = 0;
                dfs(i,j);
                if(flag == 0)  //全部被淹
                    ans++;
            }
    cout<<ans<<endl;
    return 0;
}