200. 岛屿数量

题目描述

给定一个由字符 "1" 和 "0" 组成的二维网格 grid：

"1" 表示陆地。
"0" 表示水。

岛屿由水平方向或垂直方向相邻的陆地连接而成。可以假设网格四周都被水包围，求网格中的岛屿数量。

注意，对角线相邻的陆地不属于同一座岛屿。

示例一：

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

输出：1

示例二：

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

输出：3

1. 把网格看成图

可以把每个陆地格子看作一个图节点，上、下、左、右相邻的陆地之间存在一条边。

这样，每座岛屿就是图中的一个连通分量。问题转化为：

二维网格中有多少个由 "1" 组成的四向连通分量？

扫描整个网格时：

遇到水或已经访问过的陆地，跳过。
遇到一块尚未访问的陆地，说明发现了一座新岛屿，答案加一。
从该格子执行 BFS 或 DFS，访问并标记属于同一岛屿的所有陆地。

搜索结束后，这座岛屿已经全部处理。继续扫描时不会重复计数。

2. 如何记录已经访问的陆地

题目只要求返回岛屿数量，搜索完成后不再需要原网格中的陆地信息，因此可以直接修改输入：

访问前："1"
访问后："0"

这个过程通常被称为“淹没岛屿”。它复用了输入网格作为访问标记，不需要额外创建 visited 矩阵。

如果业务场景要求保留原始输入，则应使用一个同样大小的布尔矩阵记录访问状态，或者先复制网格。

3. BFS 解法

BFS 使用队列逐层访问与起点相连的所有陆地。

队列中保存：

已经发现，但邻居尚未全部检查的陆地坐标

处理过程：

将新岛屿的起点标记为水并加入队列。
从队列中取出一个格子。
检查它的四个相邻格子。
如果邻居在网格内并且是陆地，立即标记并加入队列。
队列为空时，整座岛屿都已被淹没。

为什么要在入队时标记

一块陆地可能同时与多个已发现格子相邻。如果等到出队时才标记，它可能在出队前被多个邻居重复加入队列。

入队时立即将 "1" 改成 "0"，可以保证每块陆地最多入队一次。

BFS 代码实现

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  if (grid.length === 0 || grid[0].length === 0) {
    return 0;
  }

  const rows = grid.length;
  const columns = grid[0].length;
  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  let islandCount = 0;

  const bfs = (startRow, startColumn) => {
    const queue = [[startRow, startColumn]];
    let head = 0;

    // 入队时立即标记，避免同一格子重复入队。
    grid[startRow][startColumn] = "0";

    while (head < queue.length) {
      const [row, column] = queue[head++];

      for (const [rowOffset, columnOffset] of directions) {
        const nextRow = row + rowOffset;
        const nextColumn = column + columnOffset;
        const isInGrid =
          nextRow >= 0 &&
          nextRow < rows &&
          nextColumn >= 0 &&
          nextColumn < columns;

        if (isInGrid && grid[nextRow][nextColumn] === "1") {
          grid[nextRow][nextColumn] = "0";
          queue.push([nextRow, nextColumn]);
        }
      }
    }
  };

  for (let row = 0; row < rows; row++) {
    for (let column = 0; column < columns; column++) {
      if (grid[row][column] === "1") {
        // 尚未访问的陆地一定属于一座此前未统计的岛屿。
        islandCount++;
        bfs(row, column);
      }
    }
  }

  return islandCount;
};

这里使用 head 指针读取队列，而不是调用 queue.shift()。JavaScript 数组的 shift() 可能移动后面的所有元素，频繁调用会产生额外开销。

4. DFS 解法

DFS 从一块陆地出发，沿一个方向不断深入，无法继续后再返回处理其他方向。

递归函数的含义是：

dfs(row, column)：淹没与 (row, column) 四向连通的所有陆地

递归终止条件包括：

坐标越过网格边界。
当前格子不是尚未访问的陆地。

只要当前格子是 "1"，就先把它修改为 "0"，再递归访问四个方向。

DFS 代码实现

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  if (grid.length === 0 || grid[0].length === 0) {
    return 0;
  }

  const rows = grid.length;
  const columns = grid[0].length;
  let islandCount = 0;

  const dfs = (row, column) => {
    const isOutOfGrid =
      row < 0 || row >= rows || column < 0 || column >= columns;

    // 越界、水以及已经访问过的陆地都不需要继续搜索。
    if (isOutOfGrid || grid[row][column] !== "1") {
      return;
    }

    // 先标记再递归，避免相邻格子互相重复访问。
    grid[row][column] = "0";

    dfs(row + 1, column);
    dfs(row - 1, column);
    dfs(row, column + 1);
    dfs(row, column - 1);
  };

  for (let row = 0; row < rows; row++) {
    for (let column = 0; column < columns; column++) {
      if (grid[row][column] === "1") {
        islandCount++;
        dfs(row, column);
      }
    }
  }

  return islandCount;
};

递归 DFS 写法简洁，但当岛屿很大、形状很狭长时，递归深度可能接近陆地数量。JavaScript 运行环境通常不会自动进行尾调用优化，可能出现调用栈溢出。此时可以使用 BFS，或者将 DFS 改写为显式栈。

5. 迭代 DFS 实现

如果希望保留 DFS 的遍历方式，又不想依赖递归调用栈，可以使用数组模拟栈：

var numIslands = function (grid) {
  if (grid.length === 0 || grid[0].length === 0) {
    return 0;
  }

  const rows = grid.length;
  const columns = grid[0].length;
  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  let islandCount = 0;

  const dfs = (startRow, startColumn) => {
    const stack = [[startRow, startColumn]];
    grid[startRow][startColumn] = "0";

    while (stack.length > 0) {
      const [row, column] = stack.pop();

      for (const [rowOffset, columnOffset] of directions) {
        const nextRow = row + rowOffset;
        const nextColumn = column + columnOffset;
        const isInGrid =
          nextRow >= 0 &&
          nextRow < rows &&
          nextColumn >= 0 &&
          nextColumn < columns;

        if (isInGrid && grid[nextRow][nextColumn] === "1") {
          grid[nextRow][nextColumn] = "0";
          stack.push([nextRow, nextColumn]);
        }
      }
    }
  };

  for (let row = 0; row < rows; row++) {
    for (let column = 0; column < columns; column++) {
      if (grid[row][column] === "1") {
        islandCount++;
        dfs(row, column);
      }
    }
  }

  return islandCount;
};

显式栈版本不会因 JavaScript 递归层数限制而报错。

6. 示例推演

使用下面的网格，其中字母便于对齐显示：

1 1 0 0
1 0 0 1
0 0 1 1

从左上到右下扫描：

第一次发现陆地

扫描到 (0, 0)：

islandCount = 1

从它执行搜索，淹没 (0, 0)、(0, 1) 和 (1, 0)：

0 0 0 0
0 0 0 1
0 0 1 1

第二次发现陆地

继续扫描到 (1, 3)：

islandCount = 2

搜索会淹没 (1, 3)、(2, 3) 和 (2, 2)：

0 0 0 0
0 0 0 0
0 0 0 0

没有剩余陆地，最终返回 2。

BFS 和 DFS 淹没格子的先后顺序可能不同，但一次搜索访问到的连通分量完全相同，因此计数结果一致。

7. 正确性说明

算法始终保持两个关键事实：

只有扫描到尚未访问的陆地时，islandCount 才加一。这块陆地不属于此前处理过的岛屿，因此确实代表一座新岛屿。
从该陆地开始的 BFS 或 DFS 会访问所有与它四向连通的陆地，并把它们标记为已访问。因此，同一座岛屿的其他格子之后不会再次触发计数。

由第一点可知，每座被统计的岛屿都是真实存在的，不会多算；由第二点可知，每座岛屿只会统计一次，也不会重复。

扫描覆盖整个网格，所以每座岛屿最终都会遇到并被统计。最终结果恰好等于岛屿数量。

8. BFS 与 DFS 如何选择

方案	搜索结构	优点	注意事项
BFS	显式队列	不依赖递归栈，JavaScript 中更稳妥	队列最宽时可能保存大量坐标
递归 DFS	函数调用栈	代码简短，递归含义直观	大型连通区域可能导致栈溢出
迭代 DFS	显式栈	不会递归栈溢出	代码量与 BFS 接近

三种实现的时间复杂度和最坏空间复杂度相同。题目只要求连通分量数量，不关心访问顺序，因此任选一种都能得到正确答案。

在 JavaScript 面试代码中，矩阵规模不确定时优先使用 BFS 或迭代 DFS；如果题目规模较小且更强调代码简洁，可以使用递归 DFS。

9. 复杂度分析

设网格大小为 m × n：

时间复杂度：O(m × n)。外层循环检查每个格子一次，每块陆地也只会被成功标记并加入搜索结构一次；每次只检查四个方向。
空间复杂度：O(m × n)。最坏情况下，队列、显式栈或递归调用栈可能包含与网格格子数同阶的坐标或调用帧。

由于直接修改了 grid，算法没有额外使用 m × n 的访问矩阵，但搜索过程本身仍可能占用线性空间。

10. 边界条件与易错点

边界条件：

空网格返回 0。LeetCode 当前约束保证网格非空，但防御性判断让函数更通用。
全部是水时，搜索从不启动，返回 0。
全部是陆地时，只启动一次搜索，返回 1。
单行或单列网格仍然使用相同的四方向判断。
对角线相邻不算连通。

易错点：

网格元素是字符串 "1" 和 "0"，不是数字 1 和 0。
发现陆地后应先增加岛屿数量，再搜索并淹没整座岛屿。
BFS 必须在入队时标记，DFS 必须在继续递归前标记。
四个方向都要检查，不能遗漏向上或向左。
下标判断必须同时覆盖行、列的上下界。
当前实现会修改输入；如果需要保留原网格，必须改用 visited 矩阵。
BFS 不建议用 shift() 反复删除队首元素。

11. 常见错误思路

每遇到一个 `"1"` 就直接计数

一座岛屿通常包含多块陆地。如果不通过搜索标记整个连通分量，会把同一座岛屿中的每块陆地分别计数。

把对角线算作连通

题目只允许水平和垂直连接。例如：

1 0
0 1

这里有两座岛屿，而不是一座。

出队或递归返回时才标记

标记过晚会让同一格子沿不同路径被重复发现，增加搜索开销，递归情况下还可能造成相互调用。应在首次发现时立即标记。

12. 与其他题目的联系

130. 被围绕的区域：同样是网格连通性问题，但它从边界出发，标记所有不能被填充的 "O"。
695. 岛屿的最大面积：每发现一个连通分量，不只计数，还要统计本次搜索访问的格子数量。
463. 岛屿的周长：需要统计陆地与水或网格边界相邻的边数。
并查集：也能维护陆地连通关系，尤其适合陆地动态加入的「岛屿数量 II」，但静态网格使用 BFS/DFS 更直接。

13. 面试追问

如果不能修改输入，代码怎么改？

创建 m × n 的布尔矩阵 visited。判断未访问陆地时同时检查 grid[row][column] === "1" 和 !visited[row][column]，首次发现时将对应位置设为 true。

如果需要岛屿的最大面积呢？

让 BFS 或 DFS 返回本次访问的陆地数量，每发现一座岛屿就用它更新最大值。外层岛屿计数框架不变。

如果陆地会动态增加呢？

每次增加陆地后重新扫描网格代价太高。可以使用并查集，把新增陆地视为一个新连通分量，再与四周已有陆地合并；每成功合并两个不同分量，岛屿数量减一。

14. 可迁移总结

统计网格连通分量的通用框架是：

扫描所有格子
  -> 发现尚未访问的目标格子，连通分量数量加一
    -> 用 BFS/DFS 标记与它连通的所有格子
      -> 继续扫描，直到覆盖整个网格

遇到岛屿、区域、连通块等题目时，优先明确四件事：

什么样的格子属于节点？
哪些方向算作相邻？
什么时候说明发现了新的连通分量？
使用原地修改还是额外 visited 记录访问状态？

这四点明确后，BFS 和 DFS 通常只是搜索结构上的不同实现。

#200. 岛屿数量

#题目描述

#1. 把网格看成图

#2. 如何记录已经访问的陆地

#3. BFS 解法

#为什么要在入队时标记

#BFS 代码实现

#4. DFS 解法

#DFS 代码实现

#5. 迭代 DFS 实现

#6. 示例推演

#第一次发现陆地

#第二次发现陆地

#7. 正确性说明

#8. BFS 与 DFS 如何选择

#9. 复杂度分析

#10. 边界条件与易错点

#11. 常见错误思路

#每遇到一个 "1" 就直接计数

#把对角线算作连通

#出队或递归返回时才标记

#12. 与其他题目的联系

#13. 面试追问

#如果不能修改输入，代码怎么改？

#如果需要岛屿的最大面积呢？

#如果陆地会动态增加呢？

#14. 可迁移总结