Number of Islands（岛屿数量）

题目 / Problem

中文： 给定一个 m × n 的二维二进制网格 grid，其中字符 '1' 表示陆地，字符 '0' 表示水，返回网格中的岛屿数量。

岛屿由水平或垂直方向相邻的陆地连接而成，并且四周被水包围。可以假设网格的四条边界之外全部是水。

只考虑上、下、左、右四个方向，对角线相邻的陆地不属于同一个岛屿。
Only horizontal and vertical adjacency counts. Diagonally adjacent land cells do not belong to the same island.

English: Given an m × n 2D binary grid grid, where '1' represents land and '0' represents water, return the number of islands.

An island is formed by horizontally or vertically adjacent land cells and is surrounded by water. You may assume all four edges of the grid are surrounded by water.

示例 / Examples

Example 1

Input:
grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

Output: 1

■ ■ ■ ■ ·
■ ■ · ■ ·
■ ■ · · ·
· · · · ·

所有陆地都能通过上下左右路径互相到达，因此只形成一个岛屿。
Every land cell is reachable from every other through horizontal or vertical moves, so there is only one island.

Example 2

Input:
grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Output: 3

■ ■ · · ·
■ ■ · · ·
· · ■ · ·
· · · ■ ■

网格中有三个互不连通的陆地区域。中间的陆地与右下方陆地只在对角线上相邻，所以它们属于不同岛屿。
The grid contains three disconnected land regions. The middle land cell is only diagonally adjacent to the bottom-right region, so they are separate islands.

约束 / Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 为字符 '0' 或 '1'。
grid[i][j] is either the character '0' or '1'.

核心思想：统计连通分量 / Key Idea: Count Connected Components

将每个陆地单元格看作图中的一个节点，上下左右相邻的陆地之间存在边。每个岛屿就是这个图中的一个连通分量。
Treat each land cell as a graph vertex, with edges between horizontally or vertically adjacent land cells. Each island is one connected component.

从左到右、从上到下扫描网格：
Scan the grid row by row:

遇到水或已经访问过的陆地时跳过。
Skip water and already visited land.
每遇到一块尚未访问的陆地，就发现了一个新岛屿，将计数加 1。
Every unvisited land cell starts a newly discovered island, so increment the count.
从该位置开始 DFS 或 BFS，将与它四方向连通的所有陆地标记为已访问。
Run DFS or BFS from that cell and mark all four-directionally connected land as visited.
继续扫描，直到整个网格处理完毕。
Continue until the whole grid is processed.

一次搜索会完整“淹没”一个岛屿，所以每启动一次新搜索，就对应一个新岛屿。
Each search completely “sinks” one island, so every new search corresponds to exactly one island.

解题思路一：迭代 DFS / Approach 1: Iterative DFS

使用栈保存等待访问的陆地位置。为了避免额外的 visited 矩阵，可以在发现陆地时立即将它从 '1' 改为 '0'，表示已经访问。
Use a stack for land cells waiting to be visited. To avoid a separate visited matrix, change each discovered cell from '1' to '0' immediately.

标记必须在位置加入栈时完成，而不是弹出时完成。否则同一个单元格可能被多个邻居重复加入栈。
Mark a cell when pushing it, not when popping it. Otherwise, multiple neighbors may add the same cell repeatedly.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {character[][]} grid
 * @return {number}
 */
function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  let islands = 0;

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] !== '1') {
        continue;
      }

      islands++;
      grid[row][col] = '0';
      const stack = [[row, col]];

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

        for (const [rowOffset, colOffset] of directions) {
          const nextRow = currentRow + rowOffset;
          const nextCol = currentCol + colOffset;

          if (
            nextRow >= 0 &&
            nextRow < rows &&
            nextCol >= 0 &&
            nextCol < cols &&
            grid[nextRow][nextCol] === '1'
          ) {
            grid[nextRow][nextCol] = '0';
            stack.push([nextRow, nextCol]);
          }
        }
      }
    }
  }

  return islands;
}

该实现会修改输入网格。如果后续仍需使用原始 grid，可以改用同尺寸的 visited 布尔矩阵，或先复制网格。
This implementation modifies the input grid. If the original grid must be preserved, use a same-sized visited matrix or copy the grid first.

执行过程 / Walkthrough

以 Example 2 为例：
For Example 2:

第一次发现陆地 / First Land Discovery

扫描到 (0,0) 时：
At (0,0):

■ ■ · · ·
■ ■ · · ·
· · ■ · ·
· · · ■ ■
↑
islands = 1

DFS 会访问 (0,0)、(0,1)、(1,0) 和 (1,1)，并将这一整块陆地标记为已访问。
DFS visits (0,0), (0,1), (1,0), and (1,1), marking the entire component as visited.

第二次发现陆地 / Second Land Discovery

之后扫描到 (2,2)：
The scan later reaches (2,2):

islands = 2

该位置没有四方向相邻的陆地，所以这个岛屿只有一个单元格。
It has no four-directionally adjacent land, so this island contains one cell.

第三次发现陆地 / Third Land Discovery

扫描到 (3,3)：
At (3,3):

islands = 3

DFS 同时访问相邻位置 (3,4)。扫描结束后没有未访问的陆地，返回 3。
DFS also visits adjacent cell (3,4). No unvisited land remains, so return 3.

复杂度 / Complexity

设网格大小为 m × n。
Let the grid size be m × n.

时间复杂度：O(mn)，每个单元格最多被扫描和访问常数次。
Time: O(mn), because each cell is scanned and visited only a constant number of times.
空间复杂度：O(mn)，最坏情况下整张网格都是陆地，栈可能保存大量位置。
Space: O(mn), because the stack may hold many cells when the entire grid is land.
修改输入作为访问标记，因此不需要额外的 O(mn) 访问矩阵。
Mutating the input removes the need for an additional O(mn) visited matrix.

解题思路二：BFS / Approach 2: Breadth-First Search

BFS 与 DFS 的岛屿计数逻辑相同，只是使用队列逐层扩散：
BFS uses the same island-counting logic but expands with a queue:

function numIslandsBFS(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  let islands = 0;

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] !== '1') {
        continue;
      }

      islands++;
      grid[row][col] = '0';
      const queue = [[row, col]];
      let front = 0;

      while (front < queue.length) {
        const [currentRow, currentCol] = queue[front++];

        for (const [rowOffset, colOffset] of directions) {
          const nextRow = currentRow + rowOffset;
          const nextCol = currentCol + colOffset;

          if (
            nextRow >= 0 &&
            nextRow < rows &&
            nextCol >= 0 &&
            nextCol < cols &&
            grid[nextRow][nextCol] === '1'
          ) {
            grid[nextRow][nextCol] = '0';
            queue.push([nextRow, nextCol]);
          }
        }
      }
    }
  }

  return islands;
}

这里使用 front 索引读取队列，避免调用 JavaScript 数组的 shift()。
An index named front reads from the queue instead of using JavaScript's shift().

BFS 的时间和空间复杂度同样是 O(mn)。
BFS also takes O(mn) time and O(mn) worst-case space.

递归 DFS 写法 / Recursive DFS Version

递归写法更短，但当 300 × 300 的网格包含一块很大的岛屿时，递归深度可能非常大，部分 JavaScript 环境会发生调用栈溢出。
The recursive version is shorter, but a large island in a 300 × 300 grid can cause deep recursion and overflow the call stack in some JavaScript environments.

function numIslandsRecursive(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  function sink(row, col) {
    if (
      row < 0 ||
      row >= rows ||
      col < 0 ||
      col >= cols ||
      grid[row][col] !== '1'
    ) {
      return;
    }

    grid[row][col] = '0';
    sink(row - 1, col);
    sink(row + 1, col);
    sink(row, col - 1);
    sink(row, col + 1);
  }

  let islands = 0;

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === '1') {
        islands++;
        sink(row, col);
      }
    }
  }

  return islands;
}

DFS、BFS 与并查集 / DFS, BFS, and Union-Find

方法 / Method	时间 / Time	最坏辅助空间 / Worst Auxiliary Space	特点 / Notes
迭代 DFS	`O(mn)`	`O(mn)`	使用栈，避免递归限制 / Stack-based; avoids recursion limits
BFS	`O(mn)`	`O(mn)`	使用队列逐层扩散 / Queue-based expansion
递归 DFS	`O(mn)`	`O(mn)`	代码短，但可能栈溢出 / Concise but may overflow
并查集 / Union-Find	近似 `O(mn)`	`O(mn)`	适合动态连通性场景 / Useful for dynamic connectivity

本题只需对静态网格计数，DFS 或 BFS 最直接。
For this static grid, DFS or BFS is the most direct approach.

易错点 / Common Pitfalls

输入元素是字符 '0' 和 '1'，不是数字 0 和 1。
Grid entries are characters '0' and '1', not numbers 0 and 1.
只考虑上下左右四个方向，对角线不连通。
Use only the four cardinal directions; diagonal cells are not connected.
每发现一块未访问陆地，只增加一次岛屿计数，然后遍历完整连通块。
Increment the island count once per unvisited land component, then traverse the whole component.
应在相邻陆地加入栈或队列时立即标记，防止重复加入。
Mark neighboring land when adding it to the stack or queue to prevent duplicates.
直接将 '1' 改为 '0' 会修改输入；若必须保留原网格，应使用 visited。
Changing '1' to '0' mutates the input; use visited if the original grid must be preserved.
大网格中的递归 DFS 可能导致调用栈溢出，迭代 DFS 或 BFS 更稳妥。
Recursive DFS may overflow on a large grid; iterative DFS or BFS is safer.

Number of Islands