#200. 岛屿数量

LeetCode 原题链接

#题目描述

给定由字符 "1"（陆地）和 "0"（水）组成的二维网格，计算岛屿数量。陆地只按上、下、左、右四个方向相连。

输入：
[
  ["1","1","0","0"],
  ["1","0","0","1"],
  ["0","0","1","1"]
]
输出：2

#题型判断

每座岛屿就是一个由陆地组成的连通分量。扫描网格时，每遇到一块尚未访问的陆地：

• 岛屿数加一。
• 从这里做一次 BFS，将整座岛屿标记为已访问。

之后扫描到同一岛屿的其他格子时，就不会重复计数。

这里的 BFS 队列保存的是“已经发现，但还没有检查四周邻居”的陆地坐标。每次从队列中取出一个坐标，检查它的上、下、左、右；如果邻居是陆地，就立即将其标记为已访问并加入队列。队列为空时，与起点相连的所有陆地都已经处理完成，也就是完整地“淹没”了一座岛屿。

#核心过程

以上面示例为例：

1. 扫描到 (0, 0)，计数变为 1，BFS 淹没 (0,0)、(0,1)、(1,0)。
2. 继续扫描到 (1, 3)，计数变为 2，BFS 淹没 (1,3)、(2,3)、(2,2)。
3. 没有剩余陆地，返回 2。

网格变化如下，1 表示尚未访问的陆地，0 表示水或已经访问的陆地：

初始网格      第一次 BFS 后   第二次 BFS 后
1100          0000           0000
1001    ->    0001     ->    0000
0011          0011           0000

#为什么这样计数是正确的

算法始终保持下面两个事实：

1. 只有扫描到尚未访问的陆地时，才会把岛屿数量加一，因此这块陆地一定属于一座此前没有统计过的岛屿。
2. 从这块陆地开始的 BFS 会访问所有与它四向相连的陆地，因此同一座岛屿的其他格子之后不会再次触发计数。

所以，每座岛屿至少会被统计一次，也至多会被统计一次，最终计数正好等于岛屿数量。

#代码实现

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 count = 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") {
        count++;
        bfs(row, column);
      }
    }
  }

  return count;
};

#复杂度分析

• 时间复杂度：O(rows × columns)。外层扫描检查每个格子一次；每块陆地也只会入队一次，并且只检查四个方向。
• 空间复杂度：O(rows × columns)。最坏情况下整张网格都是陆地；当前实现通过移动 head 读取队列，不会删除已经处理的坐标，因此队列数组最多会保存所有陆地坐标。

#边界与易错点

• LeetCode 原题保证网格非空；代码仍保留了空网格判断，使它也适用于更通用的调用场景。
• 网格元素是字符串 "1"、"0"，不是数字。
• 对角线不算连通。
• 代码会原地修改 grid。若必须保留输入，应使用单独的 visited 集合或布尔矩阵。
• 必须在入队时标记访问，不能等到出队后再标记。

为什么必须在入队时标记？假设两块已出队的陆地拥有同一个尚未访问的邻居：如果等到这个邻居出队时才标记，那么它可能在此之前被重复加入队列。入队时立即标记，可以保证每块陆地最多入队一次。

#BFS 与 DFS 如何选择

本题也可以使用 DFS：每发现一块新陆地，就递归访问与它相连的所有陆地。两种方案的时间复杂度都是 O(rows × columns)，最坏空间复杂度也都是 O(rows × columns)。

• BFS 使用显式队列，不依赖函数调用栈，更适合 JavaScript 中规模较大的网格。
• DFS 递归写法通常更短，但岛屿很大时递归层数可能过深，导致调用栈溢出；也可以改写为使用显式栈的迭代 DFS。
• 并查集同样能统计连通分量，但需要维护额外的数据结构，本题使用 BFS 或 DFS 更直接。