最小堆边界扩张 / Priority Flood

有序前沿与路径 · HTML

数学 / 逻辑形态

把所有源边界入最小堆。弹出有效高度 h 的边界格 u；邻格 v 的有效高度为 max(h, raw[v])，局部贡献由 h 与 raw[v] 的差定义。

识别信号

• 过程从外圈、多源或已知安全边界向内部推进。
• 内部状态取决于目前最低可泄边界或最高已跨屏障。
• 局部低值不能单独决定结果，必须知道与外界连通的边界。
• 需要二维地形的蓄积、淹没、传播阈值或围困分析。

容易误判的相似信号

核心不变量

堆中是已发现区域与未知区域之间的有效边界；最小非过期边界弹出时，它给出该位置从外界首次可达的最低控制高度。

状态、转移与处理顺序

Python 骨架

import heapq

def priority_flood(height):
    if not height or not height[0]:
        return 0
    rows, cols = len(height), len(height[0])
    heap, seen = [], set()
    for r in range(rows):
        for c in (0, cols - 1):
            if (r, c) not in seen:
                seen.add((r, c)); heapq.heappush(heap, (height[r][c], r, c))
    for c in range(cols):
        for r in (0, rows - 1):
            if (r, c) not in seen:
                seen.add((r, c)); heapq.heappush(heap, (height[r][c], r, c))
    total = 0
    while heap:
        level, r, c = heapq.heappop(heap)
        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 and (nr, nc) not in seen:
                seen.add((nr, nc))
                total += max(0, level - height[nr][nc])
                heapq.heappush(heap, (max(level, height[nr][nc]), nr, nc))
    return total

正确性思路

1. 外边界是外界进入内部的全部入口，多源初始化不遗漏任何泄路。
2. 弹出的最低有效边界若可被更低路线触达，那条路线的前沿应先在堆中出现，矛盾。
3. 邻格的最低控制高度必为 max(当前边界,自身高度)；低于边界的差值正是被边界约束的局部量。

复杂度

边界条件

• 少于三行或三列时通常没有内部区域。
• 四个角在双重边界循环中必须去重。
• 非矩形输入应拒绝或预处理。
• visited 应在发现时设置，避免多个边界重复压入同一格。

错误模式

选择与排除规则

• 二维局部量由全局外边界控制：考虑 priority flood。
• 若只是可达区域，不需要边界优先级，退回 flood fill。
• 若目标是某单一路径的瓶颈，使用 minimax-dijkstra 而非累计整个区域。

相关模板

原创微型例子

Recall prompts

• 为什么必须从整个外边界同时开始？
• 为何邻格入堆值是 max(level,raw)？
• priority flood 与单路径 minimax 的目标有何差别？

我的补充