vvrf / DSA.log

问题拆解

网格里 '1' 是陆地、'0' 是水，上下左右相连的陆地算同一座岛，数一共有几座岛。

这本质是数连通分量：把每个格子看作图的节点，相邻陆地之间有边，岛的数量就是陆地节点构成的连通分量个数。数连通分量的标准做法是：扫描所有节点，遇到一个没访问过的陆地，计数器加一，然后从它出发把整个连通分量全部标记掉——这样同一座岛只会在第一次被撞见时贡献一次计数。

计数发生在“撞见新大陆”的那一刻；随后的 DFS 不产生计数，它的职责只是把这座岛从地图上抹掉，防止重复计数。

标记有个省空间的技巧：不开 visited 数组，直接把访问过的 '1' 原地改成 '0'。“访问过的陆地”和“水”在算法眼里等价——都是“不需要再进去”的格子，两种状态合并不丢失任何信息。代价是修改了输入，力扣的评测不检查这一点；若工程上不允许改输入，再把 visited 加回来即可。

DFS 淹没法

public int numIslands(char[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                count++;       // 撞见新大陆
                sink(grid, i, j); // 把整座岛淹掉
            }
        }
    }
    return count;
}

private void sink(char[][] grid, int i, int j) {
    // 越界或不是陆地，停止
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
        return;
    }
    grid[i][j] = '0'; // 原地标记，代替 visited
    sink(grid, i - 1, j);
    sink(grid, i + 1, j);
    sink(grid, i, j - 1);
    sink(grid, i, j + 1);
}

def numIslands(grid: list[list[str]]) -> int:
    m, n = len(grid), len(grid[0])

    def sink(i: int, j: int) -> None:
        # 越界或不是陆地，停止
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != "1":
            return
        grid[i][j] = "0"  # 原地标记，代替 visited
        sink(i - 1, j)
        sink(i + 1, j)
        sink(i, j - 1)
        sink(i, j + 1)

    count = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == "1":
                count += 1  # 撞见新大陆
                sink(i, j)  # 把整座岛淹掉
    return count

func numIslands(grid [][]byte) int {
    m, n := len(grid), len(grid[0])
    var sink func(i, j int)
    sink = func(i, j int) {
        // 越界或不是陆地，停止
        if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1' {
            return
        }
        grid[i][j] = '0' // 原地标记，代替 visited
        sink(i-1, j)
        sink(i+1, j)
        sink(i, j-1)
        sink(i, j+1)
    }

    count := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == '1' {
                count++    // 撞见新大陆
                sink(i, j) // 把整座岛淹掉
            }
        }
    }
    return count
}

pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
    fn sink(grid: &mut Vec<Vec<char>>, i: i32, j: i32) {
        // 越界或不是陆地，停止；用 i32 让 i-1 不会下溢
        if i < 0 || i >= grid.len() as i32 || j < 0 || j >= grid[0].len() as i32
            || grid[i as usize][j as usize] != '1'
        {
            return;
        }
        grid[i as usize][j as usize] = '0'; // 原地标记，代替 visited
        sink(grid, i - 1, j);
        sink(grid, i + 1, j);
        sink(grid, i, j - 1);
        sink(grid, i, j + 1);
    }

    let mut grid = grid;
    let mut count = 0;
    for i in 0..grid.len() {
        for j in 0..grid[0].len() {
            if grid[i][j] == '1' {
                count += 1; // 撞见新大陆
                sink(&mut grid, i as i32, j as i32); // 把整座岛淹掉
            }
        }
    }
    count
}

sink 的写法是“先递归、进门再检查”：把越界和非陆地的判断统一放在函数开头，四个方向的调用就不用各自加条件，代码短且不易漏。要强调一遍为什么不需要 visited：格子只有“待访问的陆地”和“不用进去”两种状态，'1' 改 '0' 后者兼任水和已访问，语义无损。而且这个标记必须在进入格子时立刻做，若放在四个递归之后，两个相邻格子会互相无限递归。网格最大 300×300，最坏情况（全是陆地）递归深度可达数万，Python 默认递归上限 1000 会爆栈——力扣的 Python 环境实际调高了上限所以能过，若在意这点可改成显式栈或 BFS，骨架完全一样。

复杂度

指标	复杂度	原因
时间	`O(mn)`	每个格子最多被访问两次：主循环一次，DFS 一次
空间	`O(mn)`	递归栈深度最坏是整片网格（全陆地时）

可以迁移的模式

数连通分量的骨架：扫描 + 撞见未访问节点计数 + 泛洪标记，岛屿最大面积（695）、封闭岛屿（1254）都是同款；
当“已访问”和某个既有状态（水）在算法上等价时，原地改值可以省掉 visited 数组；
网格 DFS 把边界检查收进递归入口，比在每个方向调用前判断更整洁、更不易错。

泛洪填充（flood fill）是网格图问题的“hello world”，先把它写到闭眼不错，再谈并查集和 BFS 的变体。