leetcode 链接：200. 岛屿数量

题目

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例：

解答 & 代码

解法一：深度优先搜索

遍历矩阵，寻找值为 ‘1’ 的位置，岛屿计数 +1，再通过深度优先搜索，将属于该岛屿的所有 ‘1’ 都置零

设矩阵 M 行 N 列，则时间复杂度 O(MN)，空间复杂度 O(MN)

在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN，即空间复杂度达到 O(MN)

class Solution {
private:
  // 深度优先搜索
  void dfs(vector<vector<char>>& grid, int row, int col)
  {
      // 递归结束条件：超出数组边界 or 当前位置的值为 '0'
      if(row < 0 || row >= grid.size() || 
          col < 0 || col >= grid[0].size() || 
          grid[row][col] == '0')
          return;
      // 将当前位置的值置为 '1'，代表已经遍历过（属于已经计数过的岛屿）
      grid[row][col] = '0';
      // 递归搜索上、下、左、右
      dfs(grid, row - 1, col);
      dfs(grid, row + 1, col);
      dfs(grid, row, col - 1);
      dfs(grid, row, col + 1);
  }
public:
  int numIslands(vector<vector<char>>& grid) {
      int rows = grid.size();            // 行数
      if(rows == 0)
          return 0;
      int cols = grid[0].size();        // 列数
      if(cols == 0)
          return 0;
      int islandsCnt = 0;                // 岛屿数量
      for(int i = 0; i < rows; ++i)
      {
          for(int j = 0; j < cols; ++j)
          {
              if(grid[i][j] == '1')    // 遍历矩阵寻找 '1'，作为根节点
              {
                  ++islandsCnt;        // 岛屿数 +1
                  dfs(grid, i, j);    // 深度优先搜索，将属于这个岛屿的所有 '1' 置零
              }
          }
      }
      return islandsCnt;
  }
};

执行结果： ``` 执行结果：通过

执行用时：20 ms, 在所有 C++ 提交中击败了 48.99% 的用户内存消耗：9.3 MB, 在所有 C++ 提交中击败了 59.28% 的用户


改进：在深度优先搜索的时候，探索上、下、左、右时，先进行判断是否需要递归，而不是等遍历到该位置时在判定是否符合递归结束条件；递归前先直接将相应位置置零
```cpp
class Solution {
private:
    // 深度优先搜索
    void dfs(vector<vector<char>>& grid, int row, int col)
    {        
        int rows = grid.size();
        int cols = grid[0].size();
        // 递归搜索上、下、左、右
        if(row - 1 >= 0 && grid[row - 1][col] == '1')    // 事先判断该方向是否需要递归
        {
            grid[row - 1][col] = '0';                    // 直接先置零，而不是等递归到该位置再置零
            dfs(grid, row - 1, col);
        }
        if(row + 1 < rows && grid[row + 1][col] == '1')
        {
            grid[row + 1][col] = '0';
            dfs(grid, row + 1, col);
        }
        if(col - 1 >= 0 && grid[row][col - 1] == '1')
        {
            grid[row][col - 1] = '0';
            dfs(grid, row, col - 1);
        }
        if(col + 1 < cols && grid[row][col + 1] == '1')
        {
            grid[row][col + 1] = '0';
            dfs(grid, row, col + 1);
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int rows = grid.size();            // 行数
        if(rows == 0)
            return 0;
        int cols = grid[0].size();        // 列数
        if(cols == 0)
            return 0;
        int islandsCnt = 0;                // 岛屿数量
        for(int i = 0; i < rows; ++i)
        {
            for(int j = 0; j < cols; ++j)
            {
                if(grid[i][j] == '1')    // 遍历矩阵寻找 '1'，作为根节点
                {
                    ++islandsCnt;        // 岛屿数 +1
                    grid[i][j] = '0';    // 直接先置零，而不是等深度优先搜索递归到该位置再置零
                    dfs(grid, i, j);    // 深度优先搜索，将属于这个岛屿的所有 '1' 置零
                }
            }
        }
        return islandsCnt;
    }
};

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 98.34% 的用户
内存消耗：9.2 MB, 在所有 C++ 提交中击败了 75.09% 的用户

解法二：广度优先搜索

和解法一思路相同，只不过将深度优先搜索替换成了广度优先搜索

思路：遍历矩阵，寻找值为 ‘1’ 的位置，岛屿计数 +1，再通过广度优先搜索，将属于该岛屿的所有 ‘1’ 都置零

设矩阵 M 行 N 列，则时间复杂度 O(MN)，空间复杂度 O(min(M, N))

在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M, N)，即空间复杂度达到 O(min(M, N)) ？

class Solution {
public:
  int numIslands(vector<vector<char>>& grid) {
      int rows = grid.size();            // 行数
      if(rows == 0)
          return 0;
      int cols = grid[0].size();        // 列数
      if(cols == 0)
          return 0;

      int islandsCnt = 0;                // 岛屿数量
      for(int i = 0; i < rows; ++i)
      {
          for(int j = 0; j < cols; ++j)
          {
              if(grid[i][j] == '1')    // 遍历矩阵寻找 '1' ，作为根节点
              {
                  ++islandsCnt;        // 岛屿数 +1
                  grid[i][j] = '0';    // 注意先置 '0'

                  // 广度优先搜索，将属于这个岛屿的'1'都置为零
                  queue<vector<int>> idxQ;
                  idxQ.push(vector<int>{i, j});
                  while(!idxQ.empty())
                  {
                      vector<int> idx = idxQ.front();
                      idxQ.pop();
                      int row = idx[0];
                      int col = idx[1];
                      // grid[row][col] = '0';    // 注意不要在这里才置零
                      if(row - 1 >= 0 && grid[row - 1][col] == '1')
                      {
                          idxQ.push(vector<int>{row - 1, col});
                          grid[row - 1][col] = '0';    // 加入队列前就置零，否则会重复搜索该节点，造成超时
                      }
                      if(row + 1 < rows && grid[row + 1][col] == '1')
                      {
                          idxQ.push(vector<int>{row + 1, col});
                          grid[row + 1][col] = '0';
                      }                           
                      if(col - 1 >= 0 && grid[row][col - 1] == '1')
                      {
                          idxQ.push(vector<int>{row, col - 1});
                          grid[row][col - 1] = '0';
                      }                            
                      if(col + 1 < cols && grid[row][col + 1] == '1')
                      {
                          idxQ.push(vector<int>{row, col + 1});
                          grid[row][col + 1] = '0';
                      }
                  }
              }
          }
      }

      return islandsCnt;
  }
};

执行结果： ``` 执行结果：通过

执行用时：48 ms, 在所有 C++ 提交中击败了 5.28% 的用户内存消耗：13.1 MB, 在所有 C++ 提交中击败了 5.02% 的用户 ```

CodeTop 企业题库

[中等] 200. 岛屿数量

题目

解答 & 代码

解法一：深度优先搜索

解法二：广度优先搜索