网格 Flood Fill

遍历与连通性 · HTML

数学 / 逻辑形态

节点为坐标 (r,c)，边由 dirs 生成，predicate 决定可进入性；一次 flood 覆盖与种子相连的全部合法格。

识别信号

• 输入是 grid、image 或 board，移动到相邻格。
• 题意出现岛屿、区域、颜色、洞或边界。
• 格子合法性可由局部值判断。
• 只需每区域访问一次，不需选择最短路线。

容易误判的相似信号

核心不变量

frontier 中每个坐标都已通过边界和谓词检查并被标记；弹出后只需扩展合法邻居。

状态、转移与处理顺序

Python 骨架

from collections import deque

def flood(grid, sr, sc, target, replacement):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    if not (0 <= sr < rows and 0 <= sc < cols):
        return 0
    if target == replacement or grid[sr][sc] != target:
        return 0
    q = deque([(sr, sc)])
    grid[sr][sc] = replacement
    area = 0
    while q:
        r, c = q.popleft()
        area += 1
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == target:
                    grid[nr][nc] = replacement
                    q.append((nr, nc))
    return area

正确性思路

1. 加入 frontier 的格子均与已覆盖区域相邻且满足谓词，不会越界。
2. 目标区域内任意格都有一条到种子的邻接路径；沿路径归纳必被发现。
3. 入队时改色等价于 visited，使每格最多入队一次并保证终止。

复杂度

边界条件

• 空矩阵或空行先防护。
• replacement 等于 target 时直接返回。
• 一行/一列仍须正确检查边界。
• 八邻接题目必须补充对角方向。

错误模式

选择与排除规则

• 规则网格先翻译为隐式图。
• 只求区域结果时 DFS/BFS 都可，超深区域偏迭代。
• 可修改输入则原地标记，否则用布尔矩阵。

相关模板

原创微型例子

Recall prompts

• 为什么 Python 负下标让边界 bug 更隐蔽？
• 何时原地改值等价于 visited？
• 四邻接改八邻接修改的是哪层抽象？

我的补充