image.png

思路1：BFS

  • 逐个扫描矩阵，如果发现有1，那么计数器cnt就 +1
  • 然后将这个发现的1的所有相邻的1全部变成0
  • 逐个重复这个操作
  • 需要注意的是，BFS在将新节点插入的时候就要改变数值，否则会有重复扫描的问题。

代码1：

  1. class Solution {
  2. public:
  3.     int dx[4] = {0, 1, 0, -1};
  4.     int dy[4] = {1, 0, -1, 0};
  5.     void bfs(vector<vector<char>>& grid, int x, int y, int row, int col) {
  6.         queue<pair<int, int>> queue_pos;
  8.         queue_pos.push({x, y});
  9.         while (!queue_pos.empty()) {
  10.             int cur_level_size = queue_pos.size();
  11.             for (int i = 0; i < cur_level_size; ++i) {
  12.                 pair<int, int> cur_pos = queue_pos.front();
  13.                 queue_pos.pop();
  14.                 int cur_x = cur_pos.first;
  15.                 int cur_y = cur_pos.second;
  16.                 //grid[cur_x][cur_y] = '0';
  18.                 // 考虑将新节点放到树上
  19.                 for (int i = 0; i < 4; i++) {
  20.                     int next_x = cur_x + dx[i];
  21.                     int next_y = cur_y + dy[i];
  22.                     if (next_x < 0 || next_x >= row || next_y < 0 || next_y >= col || grid[next_x][next_y] == '0') {
  23.                         continue;
  24.                     } else {
  25.                         // 此处的0起到标记的作用，防止重复访问
  26.                         grid[next_x][next_y] = '0';
  27.                         queue_pos.push({next_x, next_y});
  28.                     }
  29.                 }
  30.             }
  31.         }
  32.     }
  34.     int numIslands(vector<vector<char>>& grid) {
  35.         if (!grid.size()) {
  36.             return 0;
  37.         }
  39.         int cnt = 0;
  40.         int row = grid.size();
  41.         int col = grid[0].size();
  42.         for (int i = 0; i < row; i++) {
  43.             for (int j = 0; j < col; j++) {
  44.                 if (grid[i][j] == '1') {
  45.                     cnt++;
  46.                     bfs(grid, i, j, row, col);
  47.                 }
  48.                 // cout << grid[i][j] << " ";
  49.             }
  50.             // cout << endl;
  51.         }
  53.         return cnt;
  54.     }
  55. };

思路2：栈式DFS

  • 在弹栈的时候加入序列（也就是变成0）
  • 和先序遍历二叉树的思路一样
  • 根节点先入栈，然后弹栈，最后将可能的节点都加入栈中

  • 脑子里面要有图，不然记不住。

    代码2：

    1. class Solution {
    2. public:
    3.   void stackDfs(vector<vector<char>>&grid, int x, int y, int row, int col) {
    4.       int dx[4] = {1, 0, -1, 0};
    5.       int dy[4] = {0, -1, 0, 1};
    6.       stack<pair<int, int>> stack_islands;
    7.       stack_islands.push({x, y});
    9.       while (!stack_islands.empty()) {
    10.           // 出栈时加入遍历序列（这里就是变成0了）
    11.           pair<int, int> cur_pos = stack_islands.top();
    12.           int cur_x = cur_pos.first, cur_y = cur_pos.second;
    13.           stack_islands.pop();
    14.           grid[cur_x][cur_y] = '0';
    16.           // 入栈
    17.           for (int i = 0; i < 4; ++i) {
    18.               int next_x = cur_x + dx[i], next_y = cur_y + dy[i];
    19.               if (next_x >= 0 && next_x < row && next_y >= 0 && next_y < col && grid[next_x][next_y] == '1') {
    20.                   stack_islands.push({next_x, next_y});
    21.               }
    22.           }
    24.       }
    25.   }
    26.   int numIslands(vector<vector<char>>& grid) {
    27.       int row = grid.size();
    28.       int col = grid[0].size();
    30.       int count_islands = 0;
    31.       for (int i = 0; i < row; ++i) {
    32.           for (int j = 0; j < col; ++j) {
    33.               if (grid[i][j] == '1') {
    34.                   count_islands++;
    35.                   stackDfs(grid, i, j, row, col);
    36.               }
    37.           }
    38.       }
    40.       return count_islands;
    41.   }
    42. };

    思路3：并查集

  • 利用node(i, j) = i * col + j将二维的点变成一维的数字

  • 遍历grid当中每一个元素，如果是'1'，那么就和它上下左右所有的‘1’放到一个集合当中。
  • 遍历grid当中每一个元素，如果find(node(i,j)) == node(i, j) && grid[i][j] == 1，说明一定是一个新的集合。统计个数即可。

  • 并查集操作可以按秩进行优化。

    代码3：

    class Solution {
private:
  int row, col;
  unordered_map<int, int> fa, r;
  int dx[4] = {0, 1, 0, -1};
  int dy[4] = {1, 0, -1, 0};
public:
  bool check_boundary(int x, int y) {
      if (0 <= x && x <= row - 1 && 0 <= y && y <= col - 1) {
          return true;
      } else {
          return false;
      }
  }

  void init(int n) {
      for (int i = 0; i <= n; i++) {
          fa[i] = i;
          r[i] = 1;
      }
  }

  int find(int x) {
      if (x == fa[x]) {
          return x;
      } else {
          fa[x] = find(fa[x]);
          return fa[x];
      }
  }

  void merge(int i, int j) {
      int x = find(i);
      int y = find(j);
      if (x != y) {
          if (r[x] <= r[y]) {
              fa[x] = y;
          } else {
              fa[y] = x;
          }

          if (r[x] == r[y]) {
              r[y] += 1;
          }
      }
  }

  int node(int i, int j) {
      return i * col + j;
  }

  int numIslands(vector<vector<char>>& grid) {
      row = grid.size(), col = grid[0].size();
      init(row * col + 5);
      for (int i = 0; i < row; i++) {
          for (int j = 0; j < col; j++) {
              if (grid[i][j] == '1') {
                  for (int k = 0; k < 4; k++) {
                      int ni = i + dx[k], nj = j + dy[k];
                      if (check_boundary(ni, nj) && grid[ni][nj] == '1') {
                          merge(node(i, j), node(ni, nj));
                      }
                  }
              }
          }
      }

      int cnt = 0;
      for (int i = 0; i < row; i++) {
          for (int j = 0; j < col; j++) {
              if (find(node(i, j)) == node(i, j) && grid[i][j] == '1') {
                  cnt += 1;
              }
          }
      }

      return cnt;
  }
};