全球变暖

DFS求解连通性问题

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char mp[N][N]; //地图
int vis[N][N]={0}; //标记是否搜过
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};    //四个方向（x，y）
int flag;                                        //用于标记这个岛中是否被完全淹没
void dfs(int x, int y){
  vis[x][y] = 1;                                 //标记这个'#'被搜过。注意为什么放在这里：后面寻找接壤土地避免重复
  if( mp[x][y+1]=='#' && mp[x][y-1]=='#' &&
      mp[x+1][y]=='#' && mp[x-1][y]=='#' )
    flag = 1;                                    //上下左右都是陆地，这是一个高地，不会淹没
  for(int i = 0; i < 4; i++){                    //继续DFS周围的陆地
    int nx = x + d[i][0], ny = y + d[i][1];      //寻找接壤土地
    if(vis[nx][ny]==0 && mp[nx][ny]=='#')        //注意为什么要判断vis[][]：剪枝
      //继续DFS未搜过的陆地，目的是标记它们
      dfs(nx,ny);                                //递归
  }
}
int main(){
  int n; cin >> n;
  for (int i = 0; i < n; i++) cin >> mp[i];
  int ans = 0 ;
  for(int i = 1; i <= n; i++)                   //DFS所有像素点
    for(int j = 1; j <= n; j++)
      if(mp[i][j]=='#' && vis[i][j]==0){
        flag = 0;                              //假设这个岛被淹
        dfs(i,j);                              //找这个岛中有没有高地，如果有,置flag=1
        if(flag == 0)   ans++;                 //这个岛被淹了，统计被淹没岛的数量
      }
  cout<<ans<<endl;
  return 0;
}

笔记：输入二维数组，for循环嵌套遍历寻找“ # ”，寻找到陆地会判断该块土地是否被淹没，再递归寻找接壤土地，最后再返回该块土地是否被淹没， vis[][] 剪枝避免重复计算

BFS求解连通性问题

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char mp[N][N];
int vis[N][N];
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};      //四个方向
int flag;
void bfs(int x, int y) {
  queue<pair<int, int>> q;
  q.push({x, y});                                  //陆地入队
  vis[x][y] = 1;                                   //标记这个'#'被搜过
  while (q.size()) {
    pair<int, int> t = q.front();                  //返回队首
    q.pop();                                       //删除队首
    int tx = t.first, ty = t.second;               //带入队首的x，y数值
    if( mp[tx][ty+1]=='#' && mp[tx][ty-1]=='#' &&
        mp[tx+1][ty]=='#' && mp[tx-1][ty]=='#' )
      flag = 1;                                    //上下左右都是陆地，不会淹没
    for (int i = 0; i < 4; i++) {                  //扩展(tx,ty)的4个邻居
      int nx = tx + d[i][0], ny = ty + d[i][1];
      if(vis[nx][ny]==0 && mp[nx][ny]=='#'){      //把陆地放进队列
        vis[nx][ny] = 1;                          //注意：这一句必不可少，标记被搜过
        q.push({nx, ny});
      }
    }
  }
}
int main() {
  int n; cin >> n;
  for (int i = 0; i < n; i++) cin >> mp[i];
  int ans = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (mp[i][j] == '#' && vis[i][j]==0) {
        flag = 0;
        bfs(i, j);
        if(flag == 0) ans++;                      //这个岛全部被淹，统计岛的数量
  }
  cout << ans << endl;
  return 0;
}

笔记：BFS使用队列的形式寻找接壤陆地，代码比DFS稍复杂点，使用STL queue 管理队列，入队的坐标格式（x，y）