题解 | #岛屿数量#

ddDFS 深度优先搜索
先递归到最深处在发散搜索

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& grid) {
      if (grid.empty()) {
        return 0;
      }
      
      int ans = 0, row = grid.size(), column = grid[0].size();
      
      for (int i = 0; i < row; i++) {
        for (int j = 0; j < column; j++) {
          if (grid[i][j] == '1') {
            dfs(grid, i, j);
            ans++;
          }
        }
      }
      return ans;
    }
  
    void dfs(std::vector<std::vector<char>> &grid, int i, int j) {
      if (grid[i][j] == '0') {
        return ;
      }
      grid[i][j] = '0';
      int row = grid.size(), column = grid[0].size();
      
      // 先从一个方向递归到最深处，然后发散搜索
      
      if (i+1 < row) {    // 下
        dfs(grid, i+1, j);
      }
      // 从最深处往多个方向搜索
      if (i-1 >= 0) {   // 上  
        dfs(grid, i-1, j);
      }
      if (j+1 < column) {  // 右
        dfs(grid, i, j+1);
      }
      if (j-1 >= 0) {  // 左
        dfs(grid, i, j-1);
      }
    }
};

BFS 广度优先搜索
使用循环加队列，依次访问邻近点并将其入队

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& grid) {
      if (grid.empty()) {
        return 0;
      }
      
      int ans = 0, row = grid.size(), column = grid[0].size();
      
      for (int i = 0; i < row; i++) {
        for (int j = 0; j < column; j++) {
          if (grid[i][j] == '1') {
            bfs(grid, i, j);
            ans++;
          }
        }
      }
      return ans;
    }
  
    void bfs(std::vector<std::vector<char>> &grid, int i, int j) {  // 队列加循环
      int row = grid.size();
      int column = grid[0].size();
      std::queue<std::pair<int, int>> queue_;
      queue_.push({i, j});
      grid[i][j] = '0';
      
      while (!queue_.empty()) {
        int i = queue_.front().first;
        int j = queue_.front().second;
        queue_.pop();
        
        if (i+1 < row && grid[i+1][j] == '1') {
          grid[i+1][j] = '0';
          queue_.push({i+1, j});
        }
        if (j+1 < column && grid[i][j+1] == '1') {
          grid[i][j+1] = '0';
          queue_.push({i, j+1});
        }
        if (i-1 >= 0 && grid[i-1][j] == '1') {
          grid[i-1][j] = '0';
          queue_.push({i-1, j});
        }
        if (j-1 >= 0 && grid[i][j-1] == '1') {
          grid[i][j-1] = '0';
          queue_.push({i, j-1});
        }
      }
    }
};