岛屿数量

LeetCode 200. 岛屿数量

题目描述

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

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

 

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1
示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

解题思路

1. 多块陆地横向或纵向相连，构成一个岛屿
2. 遍历二维数组，遇到陆地，就将其周围的陆地都标记为水，直到遇到水为止，岛屿数量+1，因为一块陆地是 1，十块陆地也是 1，因此遇到陆地就可以先计数+1，然后相邻的陆地全部标记为水，这样就不会重复计数了
3. 递归遍历，直到遇到水为止
4. 时间复杂度 O(m*n)
5. 空间复杂度 O(m*n)
6. 递归深度最大为 m*n
7. 递归停止条件：越界、遇到水、已经遍历过的陆地
8. 深度遍历优先

代码

var numIslands = function (grid) {
  // 岛屿计数
  let count = 0;
  // 遍历矩阵
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] == 1) {
        // 岛屿数量+1
        count++;
        // 进行沉岛操作
        turnZero(grid, i, j);
      }
    }
  }

  // 找到岛屿后 把相邻的岛屿全部设置为海 因为是求数量 只留一块即可
  // 沉岛 函数
  function turnZero(grid, i, j) {
    // 如果到了边界 则不需要操作
    if (grid[i]?.[j] === undefined) return;
    //  已经是海洋 不需要再次操作
    if (grid[i][j] == 0) return;
    // 对自己和上下左右进行沉岛，也就是变为 0
    grid[i][j] = 0;
    turnZero(grid, i - 1, j);
    turnZero(grid, i, j + 1);
    turnZero(grid, i + 1, j);
    turnZero(grid, i, j - 1);
  }
  return count;
};

为什么不会重复计数

因为遍历的时候，遇到陆地后马上进行 DFS 深度遍历优先递归相邻的元素，在下一次遍历前会把陆地全部变为水，这样就不会重复计数了。