算法 - 岛屿数量 (Number of Islands)

Posted on

1. 题目

给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。岛屿由水平或垂直方向上相邻的陆地连接形成，且四周都被水包围。

示例:

1
2
3
4
5
6
输入:
[["1","1","0","0","0"],
 ["1","1","0","0","0"],
 ["0","0","1","0","0"],
 ["0","0","0","1","1"]]
输出: 3

2. 解题思路

典型的洪水填充（Flood Fill）/ 连通块计数。

遍历每个格子：

  • 遇到 '1'，说明发现一座还没统计过的岛屿，count++。
  • 立刻从该点做一次 DFS/BFS，把与它四连通的所有 '1' 全部「淹掉」（标记为 '0' 或写入 visited），这样同一座岛不会重复计数。
  • 继续扫描，直到所有格子处理完。

「淹掉」即去重：一座岛只需在遇到它的第一个陆地格时计一次，之后整片都变 '0' 就不会再触发计数。

  • 时间复杂度：O(m × n)，每个格子最多访问常数次。
  • 空间复杂度：O(m × n) 最坏（递归栈或队列，全陆地时）。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
function numIslands(grid: string[][]): number {
    if (grid.length === 0) return 0;
    const m = grid.length;
    const n = grid[0].length;

    // DFS 淹没整座岛
    function sink(r: number, c: number): void {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== "1") {
            return;
        }
        grid[r][c] = "0"; // 标记已访问（淹掉）
        sink(r + 1, c);
        sink(r - 1, c);
        sink(r, c + 1);
        sink(r, c - 1);
    }

    let count = 0;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === "1") {
                count++;
                sink(r, c);
            }
        }
    }
    return count;
}

// BFS 版（防止超深网格递归爆栈）
function numIslandsBFS(grid: string[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const dirs = [
        [1, 0], [-1, 0], [0, 1], [0, -1],
    ];
    let count = 0;

    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] !== "1") continue;
            count++;
            grid[r][c] = "0";
            const queue: [number, number][] = [[r, c]];
            while (queue.length) {
                const [x, y] = queue.shift()!;
                for (const [dx, dy] of dirs) {
                    const nx = x + dx;
                    const ny = y + dy;
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === "1") {
                        grid[nx][ny] = "0";
                        queue.push([nx, ny]);
                    }
                }
            }
        }
    }
    return count;
}

4. 面试延伸

  • DFS 爆栈风险：超大网格（如 1000×1000 全陆地）递归深度可达百万级，BFS 或显式栈更稳，这是全栈工程意识的加分点。
  • 不允许修改原网格？ 用 visited 布尔矩阵替代「淹成 0」，逻辑不变。
  • 岛屿最大面积（695）/ 岛屿周长（463）：DFS 时顺带累加面积 / 统计临海面数。
  • 封闭岛屿、地图分析（多源 BFS 求离陆地最远的海） 都是 Flood Fill 家族的变体。
  • 并查集解法：把相邻陆地 union，最后数连通分量，能顺带动态加陆地，体现数据结构选型能力。
  • 四连通 vs 八连通（含对角）只需增减 dirs，注意题意。

难度：中等 | LeetCode 200 题 | DFS/BFS 网格模板