Vertices are cells (r,c), dirs generates edges, and a predicate controls admission. One flood reaches every eligible cell connected to the seed.
Recognition signals
The input is a grid, image, or board with local moves.
The story mentions islands, regions, colors, holes, or boundaries.
Cell eligibility is decidable from local values.
Each region needs one visit and no shortest route is requested.
False friends
Signal
Why it is different
Direction-restricted path counting
When moves form a DAG and the goal is a count, use grid-dp.
Unequal-cost grid routing
Plain flood fill does not optimize cost; use an ordered frontier.
Core invariant
Every cell in the frontier has passed bounds and predicate checks and is already marked; expansion only considers its eligible neighbors.
State, transition, and processing order
Item
Definition
State
Cell coordinate, visited representation or in-place mark, direction set, and optional region summaries such as area or boundary flags.
Transition
Generate each neighboring coordinate, check bounds before access, check eligibility and visited, then mark and enqueue or push.
Frontier / order
A stack or queue; the order changes the trace but not the maximal region obtained.
Python skeleton
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
Correctness sketch
Every admitted cell is eligible and adjacent to the reached region, so the search cannot escape it.
Every target cell has a neighbor path to the seed; induction along that path proves discovery.
Marking on enqueue gives at most one enqueue per cell and guarantees termination.
Complexity
Time
Space
Parameters
O(RC)
O(RC)
R and C are grid dimensions; actual work may equal one region's area, with full-grid worst case.
Edge cases
Guard an empty matrix or row.
Return immediately when replacement equals target.
One-row and one-column grids still need bounds checks.