Seed every source boundary in a min-heap. Pop boundary cell u at effective height h; neighbor v receives effective height max(h,raw[v]), with local contribution derived from h versus raw[v].
Recognition signals
Expansion starts from an outer ring, multiple sources, or a known safe boundary.
Interior state depends on the lowest current outlet or highest crossed barrier.
A local low value is insufficient without connectivity to the exterior.
The task models accumulation, flooding, propagation thresholds, or enclosure on a 2D terrain.
False friends
Signal
Why it is different
Single-source shortest path
The heap key here is commonly effective boundary height, not an additive route sum.
Independent row or column scans
A two-dimensional outlet can route around local extrema, so one-dimensional scans miss connectivity.
Core invariant
The heap is the boundary between discovered and unknown regions; its minimum fresh cell has the lowest possible controlling height at first contact from the exterior.
State, transition, and processing order
Item
Definition
State
Multi-source min-heap, visited cells, raw values, effective height, and optional accumulated contribution.
Transition
From boundary u(h), discover v, mark it, add max(0,h-raw[v]), and push max(h,raw[v]) as its effective boundary.
Frontier / order
A heap for the entire discovered/unknown boundary, not merely the endpoint of one route.
Python skeleton
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
Correctness sketch
The exterior boundary contains every entry route from outside, so multi-source initialization omits no outlet.
If a popped minimum effective boundary had a lower exterior route, that route's frontier would already have appeared earlier in the heap.
A newly reached cell's minimum controlling height is exactly max(current boundary, own height); any gap below the boundary is the locally constrained amount.
Complexity
Time
Space
Parameters
O(RC log(RC))
O(RC)
Each cell is discovered and pushed at most once; the heap may contain O(RC) cells.
Edge cases
With fewer than three rows or columns, there is usually no interior.
Deduplicate corners touched by both boundary loops.
Reject or normalize a ragged matrix.
Mark on discovery to prevent duplicate pushes from several boundary cells.
Error patterns
Pattern
Why it fails / fix
Pushing raw instead of effective height
A low cell falsely becomes a new outlet; push max(level,raw).
Starting from one corner
Other exterior entries are omitted, corrupting the boundary model.
Marking only after pop
Several boundary neighbors can push one cell and count its contribution repeatedly.
Selection and exclusion rules
Consider priority flood when a 2D local value is controlled by global exterior boundaries.
Return to ordinary flood fill when frontier priority is irrelevant.
For one route's bottleneck rather than a whole region's accumulation, use minimax-dijkstra.