LeetCode 200. 岛屿数量
题目核心
给定一个由字符 '1' 和 '0' 组成的二维网格 grid：
'1'表示陆地。'0'表示水。
上下左右相邻的陆地会连成一个岛屿，斜着相邻不算连接。题目要求统计网格中一共有多少个岛屿。
例如：
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1答案：3 个岛屿。
解题思考过程
第一步：理解问题
这是一个典型的图遍历问题。每个岛屿是一个连通分量，我们需要统计连通分量的数量。
第二步：暴力解法（DFS）
最直接的思路：遍历每个格子，如果是陆地（'1'），就从这里开始进行深度优先搜索，把所有相连的陆地标记为已访问（比如改成'0'），然后岛屿数量加1。
遍历 grid[i][j]:
if grid[i][j] == '1':
dfs(i, j) - 把这个岛屿的所有'1'都变成'0'
count++为什么要把'1'变成'0'？因为这样可以避免重复计数。当我们再次遍历到这个格子时，它已经是'0'了，不会再被当成新的岛屿。
第三步：DFS 的实现
DFS 需要访问当前格子的上下左右四个方向：
dfs(i, j):
if i < 0 or i >= rows or j < 0 or j >= cols: return
if grid[i][j] != '1': return
grid[i][j] = '0' // 标记为已访问
dfs(i-1, j) // 上
dfs(i+1, j) // 下
dfs(i, j-1) // 左
dfs(i, j+1) // 右第四步：BFS 作为替代
除了 DFS，也可以用 BFS（广度优先搜索）：
用队列存储待访问的格子
while 队列不为空:
取出队首格子
把它的上下左右的'1'加入队列，并标记为'0'两种方法的时间复杂度都是 O(m*n)，因为每个格子最多访问一次。
第五步：为什么这种方法能工作
每个岛屿是一个连通分量，我们通过 DFS/BFS 把整个连通分量都标记为已访问（变成'0'），这样每个连通分量只会被计数一次。
时间复杂度：O(m*n) - 每个格子最多访问一次
空间复杂度：O(m*n) - 最坏情况下，整个网格都是陆地，DFS/BFS 的栈/队列大小是 O(m*n)第六步：边界情况
- 空网格：返回 0 ✓
- 全是'0'：返回 0 ✓
- 全是'1'：返回 1 ✓
- 单个格子'1'：返回 1 ✓
0 0 0 1 1这个网格中共有 3 个岛屿。
核心思路：发现一块陆地，就淹没整座岛
从左到右、从上到下遍历网格。
当遇到一个还没有访问过的 '1' 时，说明发现了一座新岛屿：
- 岛屿数量加
1。 - 从这个位置开始 DFS。
- 把与它上下左右相连的所有
'1'都改成'0'。
这个过程可以理解为“淹没”当前整座岛。之后继续遍历时，这座岛上的陆地已经全部变成 '0'，不会被重复计数。
遇到新的 1 -> count++ -> DFS 淹没整座岛 -> 继续寻找下一个 1当前代码需要修正的地方
当前代码的遍历和 DFS 思路是正确的，但是 dfs 定义在 numIslands 函数外部：
var numIslands = function (grid) {
const m = grid.length;
const n = grid[0].length;
// ...
};
function dfs(i, j) {
// 这里使用了 m、n 和 grid
}m、n、grid 都属于 numIslands 的局部作用域，外部的 dfs 无法访问它们，运行时会出现变量未定义的问题。
最直接的修改方式是把 dfs 放进 numIslands 内部。这样它可以通过闭包直接使用 grid、m 和 n。
DFS 解法
var numIslands = function (grid) {
const m = grid.length;
const n = grid[0].length;
let count = 0;
const dfs = (i, j) => {
if (
i < 0 ||
i >= m ||
j < 0 ||
j >= n ||
grid[i][j] === "0"
) {
return;
}
grid[i][j] = "0";
dfs(i - 1, j);
dfs(i + 1, j);
dfs(i, j - 1);
dfs(i, j + 1);
};
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === "1") {
count++;
dfs(i, j);
}
}
}
return count;
};DFS 的终止条件
DFS 开始后会向上、下、左、右四个方向搜索：
dfs(i - 1, j);
dfs(i + 1, j);
dfs(i, j - 1);
dfs(i, j + 1);但不是每个方向都能继续，所以函数开头需要处理五种不能继续搜索的情况：
if (
i < 0 ||
i >= m ||
j < 0 ||
j >= n ||
grid[i][j] === "0"
) {
return;
}前四个条件表示坐标已经超出网格边界，最后一个条件表示当前位置是水，或者是已经访问过的陆地。
遇到这些情况时，当前搜索路线结束，直接返回。
为什么要先把 1 改成 0
访问陆地后，要立刻执行：
grid[i][j] = "0";它的作用是标记当前位置已经访问过。
假设有两块相邻陆地：
1 1左边会递归访问右边，右边又可以递归访问左边。如果不做访问标记，它们就会不断互相调用，最终造成无限递归。
先把当前位置改成 '0' 后，再从相邻位置回到这里时，会命中终止条件并返回。
完整遍历过程
以这个网格为例：
1 1 0
0 1 0
1 0 1遍历到左上角 (0, 0) 时第一次遇到 '1'：
count = 1从 (0, 0) 开始 DFS，会淹没与它连通的三个位置：
0 0 0
0 0 0
1 0 1继续遍历，在 (2, 0) 遇到新的 '1'：
count = 2淹没后继续遍历，又在 (2, 2) 遇到新的 '1'：
count = 3最终返回 3。
为什么 count 只在外层遍历中增加
一次 DFS 会处理整座相连的岛屿。DFS 内部遇到的其他 '1'，只是当前岛屿的一部分，不是新的岛屿。
因此只有外层遍历发现一个尚未访问的 '1' 时，才执行：
count++;可以把外层遍历理解成“找岛”，把 DFS 理解成“确认并标记这座岛的全部范围”。
复杂度
设网格有 m 行、n 列：
- 时间复杂度：
O(m * n)，每个格子最多被访问有限次。 - 空间复杂度：最坏为
O(m * n)，来自递归调用栈。当所有格子都是陆地时，递归可能深入整张网格。
原地标记的影响
把 '1' 改成 '0' 不需要额外的访问数组，写法简单，也节省了额外空间。但它会改变传入的原始 grid。
如果题目要求保留原网格，可以创建一个 visited 数组：
const visited = Array.from({ length: m }, () => Array(n).fill(false));访问陆地时把 visited[i][j] 改为 true，并在终止条件中判断它。不过本题不要求保留输入，所以直接修改 grid 更方便。
替代解法：BFS
也可以在发现新岛屿后，用队列进行广度优先搜索。每次取出一块陆地，再把它周围还未访问的陆地加入队列。
var numIslands = function (grid) {
const m = grid.length;
const n = grid[0].length;
const directions = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
];
let count = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] !== "1") {
continue;
}
count++;
grid[i][j] = "0";
const queue = [[i, j]];
let front = 0;
while (front < queue.length) {
const [row, col] = queue[front++];
for (const [dr, dc] of directions) {
const nextRow = row + dr;
const nextCol = col + dc;
if (
nextRow >= 0 &&
nextRow < m &&
nextCol >= 0 &&
nextCol < n &&
grid[nextRow][nextCol] === "1"
) {
grid[nextRow][nextCol] = "0";
queue.push([nextRow, nextCol]);
}
}
}
}
}
return count;
};DFS 和 BFS 的时间复杂度都是 O(m * n)。DFS 写法更短、更贴近当前代码；BFS 不依赖很深的递归调用栈，在网格非常大时更稳妥。