leetcode：200. 岛屿数量

题目

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

示例：

  1. 输入：grid = [
  2.   ["1","1","1","1","0"],
  3.   ["1","1","0","1","0"],
  4.   ["1","1","0","0","0"],
  5.   ["0","0","0","0","0"]
  6. ]
  7. 输出：1
  1. 输入：grid = [
  2.   ["1","1","0","0","0"],
  3.   ["1","1","0","0","0"],
  4.   ["0","0","1","0","0"],
  5.   ["0","0","0","1","1"]
  6. ]
  7. 输出：3

image.png

解答 & 代码

解法一：深度优先搜索 DFS

深度优先搜索（DFS）遍历二维数组。（实际上就类似于 DFS 遍历二叉树）
遍历矩阵，寻找值为 ‘1’ 的位置，岛屿计数 +1，再通过深度优先搜索，将属于该岛屿的所有 ‘1’ 都置零

  1. class Solution {
  2. private:
  3.     // 深度优先搜索，从位置 (row, col) 开始，将与之相邻的都置 0
  4.     void dfs(vector<vector<char>>& grid, int row, int col)
  5.     {        
  6.         int rows = grid.size();
  7.         int cols = grid[0].size();
  8.         // 递归结束条件：越界 or 已经是海水
  9.         if(row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0')
  10.             return;
  11.         // 将 (row, col) 位置置 0
  12.         grid[row][col] = '0';
  13.         // 递归搜索上、下、左、右，将当前岛屿的每个位置都变为 0
  14.         dfs(grid, row - 1, col);
  15.         dfs(grid, row + 1, col);
  16.         dfs(grid, row, col - 1);
  17.         dfs(grid, row, col + 1);
  18.     }
  19. public:
  20.     int numIslands(vector<vector<char>>& grid) {
  21.         int rows = grid.size();            // 行数
  22.         if(rows == 0)
  23.             return 0;
  24.         int cols = grid[0].size();        // 列数
  25.         if(cols == 0)
  26.             return 0;
  28.         int islandsCnt = 0;                // 岛屿数量
  29.         for(int i = 0; i < rows; ++i)
  30.         {
  31.             for(int j = 0; j < cols; ++j)
  32.             {
  33.                 if(grid[i][j] == '1')    // 遍历矩阵寻找 '1'，作为根节点
  34.                 {
  35.                     ++islandsCnt;        // 岛屿数 +1
  36.                     dfs(grid, i, j);    // 深度优先搜索，将属于这个岛屿的所有 '1' 置零
  37.                 }
  38.             }
  39.         }
  41.         return islandsCnt;
  42.     }
  43. };

复杂度分析：设矩阵 M 行 N 列

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

执行结果：

  1. 执行结果：通过
  3. 执行用时：28 ms, 在所有 C++ 提交中击败了 89.21% 的用户
  4. 内存消耗：11.9 MB, 在所有 C++ 提交中击败了 82.95% 的用户

解法二：广度优先搜索 BFS

[中等] 200. 岛屿数量