连通图的遍历

“连通块问题”，是基础搜索。用DFS或BFS都行：遍历一个连通块（找到这个连通块中所有的’#‘，并标记已经搜过，不用再搜）；再遍历下一个连通块…；遍历完所有连通块，统计有多少个连通块。

全球变暖

题目链接：全球变暖

步骤：

1. 对图g[N][N]进行循环，每次从是陆地并且没有遍历过的点开始搜索
2. 进入dfs函数，将当前搜到的点置为true
3. 然后以此点为中心向四个方向遍历，直到周围没有满足条件（即是陆地又没遍历过的）的点
4. 便会开始向上回溯直到一步步回溯到退出dfs函数
5. 如果本次找到的连通块中有一个点其四个方向都是陆地，则这个岛屿不会被完全淹没，否则会被完全淹没。

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;

int n;
int st[N][N];
char g[N][N];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向
int flag,ans=0;

void dfs(int i,int j){
    st[i][j] = 1;
    // cout << "ij:"<< i << " " << j << "\n";
    if(g[i+1][j]=='#' && g[i-1][j]=='#' && g[i][j+1]=='#' && g[i][j-1]=='#'){
        flag = 1;
    }
    //继续DFS周围的陆地
    for(int a=0;a<4;a++){
        int x = i+dx[a]; int y = j+dy[a];
        //继续DFS未搜过的陆地，目的是标记它们   
        //if(nx>=1 && nx<=n && ny>=1 && ny<=n && vis[nx][ny]==0 && a[nx][ny]=='#') //题目说边上都是水，所以不用这么写了
        if(!st[x][y] && g[x][y] == '#'){
            dfs(x,y);
            // cout << x << " " << y << "\n";
        }
    }
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >> g[i][j];
        }
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(g[i][j] == '#' && !st[i][j]){
                flag = 0;
                dfs(i,j);
                // cout << "本次连通图查找完毕" << "\n";
                if(flag == 0){ //这个岛全部被淹
                    ans++; //统计被淹的岛的数量
                    
                }
            }
        }
    }
    cout << ans;
    return 0;
}