LeetCode 200. 岛屿数量：网格 DFS/BFS 与「 Flood Fill 」

题目：网格里的「连通块计数」

LeetCode 200：m × n 的二维网格，'1' 是陆地、'0' 是水，求岛屿数量——岛屿 = 水平或垂直相邻的陆地组成的连通块（斜向不算）。

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

网格即图：把每个格子看作图节点——「相邻的陆地格子」是边——岛屿 = 连通分量——「数岛屿」=「数连通分量」——这是图论问题穿上了网格的外衣——识别这一层，算法就只剩「图的遍历」——「DFS 或 BFS」都行。

解法一：DFS 的「沉岛」

主循环与标记：遍历每个格子——遇到未访问的 '1' → 岛屿数 +1 → DFS 把整个岛「淹掉」（访问过的 '1' 改成 '0'——「沉岛」防止重复计数与死循环——不标记则无限递归——「标记」是图遍历的生命线：

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return                          # 越界
        if grid[r][c] != '1':
            return                          # 水或已访问
        grid[r][c] = '0'                    # 沉岛标记
        dfs(r+1, c); dfs(r-1, c)           # 上下
        dfs(r, c+1); dfs(r, c-1)           # 左右

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

「越界检查」的位置：放在递归入口（先检查再干活——「入口检查」的简洁（四个方向的递归调用无需再判——「检查与干活的位置」约定决定代码的简洁度。「原地修改」与「visited 集合」的取舍：沉岛修改原网格——「省空间 O(1) 额外」但「破坏输入」（如果调用者还要用原网格——「只读要求」的场景——用 visited 集合（O(mn) 空间——「面试时主动说明取舍」：默认沉岛、如需保留原数据用 visited——「说明取舍」是高级感的来源。DFS 的递归深度：最坏情况（全岛）递归深度 m×n——「栈溢出」的风险（大网格（1000×1000）——「Python 的递归限制」（默认 1000——「改用显式栈」（DFS 的迭代化——「栈保存待访问格子」——与有效括号篇的栈思想呼应。

解法二：BFS 的队列

BFS 的流程：同样主循环找 '1' → 队列保存起点 → 出队时检查四邻、入队未访问邻居——「BFS 的标记时机」：「入队时标记」（不是出队时——出队时标记会导致重复入队（同一格子被多个邻居入队——「入队即标记」是 BFS 的铁律——DFS 没有这个问题（递归天然标记一次——「DFS 与 BFS 的标记时机差异」是网格题的常见坑。

from collections import deque

def num_islands_bfs(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                grid[r][c] = '0'
                queue = deque([(r, c)])
                while queue:
                    cr, cc = queue.popleft()
                    for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                        nr, nc = cr+dr, cc+dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                            grid[nr][nc] = '0'   # 入队时标记
                            queue.append((nr, nc))
    return count

「BFS 的迭代无栈风险」——大网格的稳健选择——「BFS 额外的能力」：层次信息（「最短距离」——BFS 天然按层扩展（「岛屿的最短桥」（LeetCode 934——多源 BFS——「多源 BFS」（多个起点同时入队——「多源 BFS」的妙用（同时从所有 1 开始扩散——「01 矩阵」的题目——「BFS 的层次性」在无权图最短路的应用——这是 BFS 相对 DFS 的独有武器。

graph TD
    A[网格=图] --> B[DFS: 递归简洁<br/>栈溢出风险]
    A --> C[BFS: 队列迭代<br/>入队即标记 · 有层次信息]
    B & C --> D[沉岛标记防重复<br/>或 visited 集合]
    E[方向数组: (1,0)(-1,0)(0,1)(0,-1)<br/>消除四份重复代码] --> B
    E --> C

复杂度与网格题家族

复杂度分析：每个格子最多访问一次——时间 O(m×n)、空间 O(min(m,n)) 到 O(m×n)（DFS 栈/BFS 队列的最坏——「时间无法更低」（每个格子至少看一次——**「下界」的论证。

网格题家族的谱系：岛屿数量（连通分量计数）、岛屿的最大面积（DFS 返回面积——「计数变求和」）、封闭岛屿（「边界接触」的排除（不靠边的岛——「先淹边界岛再数」的两次遍历技巧——「预处理」的思路、「统计包围的水」（LeetCode 130 被围绕的区域——「反向思维」（找不被包围的 O——「正难则反」的解题策略——「网格题的通用心法」：网格即图、遍历+标记、DFS/BFS 任选——「方向数组」消除重复、「标记时机」是 DFS/BFS 各自的坑——掌握了「岛屿数量」就掌握了整个网格家族的骨架。

网格遍历的进阶：多源 BFS 与「网格 DP」

网格遍历的进阶：多源 BFS 的原理与网格上的动态规划。「多源 BFS」的原理：「多个起点同时入队」：「超级源点」（虚拟起点连接所有真实起点——「多源的最短路」（从所有源同时扩散——「第一个到达的时间」（每个格子被最近的源到达——「多源 BFS 的语义」：「到最近源的距离」——「应用 1：01 矩阵」（每个 0 到最近 1 的距离——「多源 BFS」（所有 1 入队——「扩散到 0」——「01 矩阵」的解法——「应用 2：腐烂的橘子」（LeetCode 994——多源扩散+分钟数——「层次 = 分钟」——「BFS 的层次计时」——「新鲜的橘子最终全腐烂吗」——「剩余的判定」——「多源 BFS 的应用清单」：火灾蔓延、疫情扩散、「扩散类问题」的通用解——「扩散」的时间维度——「BFS 的层次=时间」的映射。「网格 DP」：「网格上的动态规划」：「不同路径（62）」（库内已有——「网格 DP 的方向」（只向右下——「无后效性」——「最小路径和（64）」——「网格 DP 的转移」——「dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])」——「方向受限」是 DP 的前提——「四方向可走」时（DP 失效——「BFS/Dijkstra」接管——「DP vs 图算法」的边界——「DAG 的 DP」与「有环的图算法」——「环」是 DP 与图算法的分水岭——「有环则用图算法」——「无环则 DP」——「网格的方向约束」决定了它是 DAG——「DP 与图算法的分界」的清晰认知。「网格题的进阶家族」：「岛屿家族」（数量/面积/封闭/周长——「家族的扩展」——「最大正方形」（DP 的另一种——「正方形的判定」——「网格的 DP 家族」——「网格=图+DP 双模式」——「看问题选模式」——「连通性→图模式，路径→DP 模式」——网格问题的两大模式。网格遍历的进阶总结：多源 BFS（超级源点、扩散计时）+网格 DP（方向约束=DAG）+DP 与图算法的分界（环）+网格家族（岛屿/正方形）——「网格」是「图+DP」双模式的最小教学场——「同一个网格」既可以是图（连通性），也可以是 DAG（路径）——「模式的切换」由问题的性质决定——「连通性问图，路径问 DP」——这一句话就是网格问题的导航图。

岛屿数量的高频问答：栈深、并查集与图像处理的亲戚

问题一：网格很大时递归 DFS 会不会栈溢出？工程上怎么办？——会：全岛的最坏情形递归深度是 m×n，1000×1000 的网格就是一百万层——Python 直接 RecursionError、C/C++ 段错误。三条工程出路：迭代化 DFS（显式栈，把递归调用换成 append/pop，逻辑等价）；BFS（队列天然无栈问题，代码也顺手）；分块处理（超大栅格按行分块、块间缝合——GIS 领域的常规手段）。顺带纠正一个常见误解：sys.setrecursionlimit 只是放宽 Python 层的检查上限，底层 C 栈的容量不会跟着涨，调太高是「把可捕获的异常换成不可捕获的崩溃」——真正的解法永远是换非递归算法，而不是调参数。

问题二：并查集也能数岛屿吗？什么场景下它是唯一解？——能：把相邻的陆地格 union 起来，最后数不同根的数量就是岛屿数（路径压缩 + 按秩合并，均摊复杂度近乎线性）。静态网格上它不如 DFS/BFS 直观，但在动态场景它是唯一解：LeetCode 305「岛屿数量 II」逐个位置加陆地、每加一块就要实时报告岛屿数——「沉岛」式的标记只能支持一次性的静态遍历，做不了增量添加；并查集的 union 天然支持增量合并、根计数天然支持实时查询。口诀：静态连通用 DFS/BFS，动态连通用并查集——305 是这句口诀的标准考题，也是「同一个问题换个时序就换算法家族」的最佳样本。

问题三：这道题与图像处理里的 flood fill 是什么关系？——同一算法：Photoshop 的油漆桶与魔棒就是从点击处做连通填充（四邻或八邻、用颜色容差代替 '1'/'0' 的判定），「沉岛」对应「填充色覆盖」。更工程化的亲戚是连通域标记（connected component labeling）：OCR 的字符提取、医学影像的病灶分割、遥感图的地块统计，底层全是它。生产实现与题解有两点差异：一是两遍扫描法更常用——第一遍逐格标临时号并记录冲突、第二遍归并重编号，比逐格 flood fill 的缓存局部性好；二是四连通与八连通要按业务定——字符识别常用八连通（斜笔画不能断），棋盘类问题常用四连通。算法题给的是模型，工程给的是约束（缓存、增量、连通性定义、可并行性）——这道题是走进那个世界的第一扇门。

问题四：网格巨大到无法整体载入内存时，怎么数岛？——外存场景把这道题推向「扫描线 + 并查集」：按行流式读入，内存里只维护当前行与上一行的连通关系——新行的每个陆地段与上一行有重叠的段就 union、没有重叠的开新编号，扫完全表数根即为岛屿数，内存只需 O(网格宽度)。这是地理信息与遥感领域的经典计数法，也是 305「动态加岛」的另一个视角：逐行处理本质上就是增量地加入陆地——静态大网格、动态加岛、流式扫描，三个场景殊途同归于并查集。至此这道题的完整图景是：小网格用 DFS/BFS 直观解决，大网格用外存扫描，动态网格用并查集——数据规模与时序换了，算法家族跟着换，这正是「网格即图」这个模型里长出的完整工程树。

小结

岛屿数量的完整解析：「网格即图」（格子是节点、相邻是边——岛屿=连通分量——数岛=数连通分量——「问题的图论化」是第一步）；DFS 沉岛（简洁递归+原地标记——越界入口检查——大网格的栈风险与显式栈）；BFS 队列（「入队即标记」的铁律、无栈风险、层次信息与多源 BFS 的独有能力）；取舍（沉岛省空间但破坏输入、visited 保输入费空间——面试主动说明）；家族谱系（面积、封闭岛屿、被围绕的区域——「网格即图+遍历标记」通吃全家族）。给学习者的建议：网格题是学习图遍历的最佳入门（比抽象的邻接表直观——格子看得见摸得着）——先在纸上把网格画成图（格子连线），然后 DFS/BFS 的代码就是「图的遍历」的直接翻译——「把不熟悉的问题翻译成熟悉的模型」是算法学习的核心方法论——网格题就是这条方法论的绝佳练习场。

岛屿数量教的是「看见网格里的图」——从此以后，迷宫、棋盘、图像处理、甚至关系网络——所有「格子+相邻」的问题，你手里都有了 DFS 与 BFS 两把钥匙。