BFS / DFS on Grids
01 / The one-sentence essence
Walk an implicit graph from a seed, marking cells as you enqueue them — a queue gives breadth (closest-first), a stack gives depth (all-one-way-first), and the rest is the same algorithm.
Problemflood from (r, c) via 4-neighbor adjacencyGrid4 × 4Start(0, 0)Modebfs
1
1
1
1
1
·
·
1
1
·
·
1
1
1
1
1
queue (1)
(0,0)
← frontStart at (0,0). Queue begins with the seed cell.
step
0 / 13
visited
0
frontier
1
current
—
0 / 13
02 / The pattern signature
# flood from (sr, sc)visited ← {(sr, sc)}frontier ← [(sr, sc)]while frontier not empty:cell ← frontier. pop_front() // BFS// or frontier.pop() // DFSfor each 4-neighbor of cell:if in bounds, traversable, not visited:mark visited; push onto frontier
03 / When to recognize this pattern
"grid / map"
The problem describes a 2D layout with adjacency — islands, mazes, rotting oranges, walls and passages.
"shortest / fewest"
You need distance from a source — minimum steps, fewest moves. BFS finds it in one pass because it expands level by level.
"reachability / connected"
You only need to know which cells are reachable, not the order — either traversal works; DFS is usually simpler recursively.
"implicit graph"
The "vertices" aren't pre-built — they're states (positions, board configurations) generated lazily by a successor function. Same algorithm; the neighbor function changes.
04 / Common pitfalls
i.
Marking visited at the wrong moment.
Mark a cell visited the moment you enqueue it, not when you pop it — otherwise you can push the same cell multiple times before it's ever processed. For BFS this breaks the shortest-path invariant; for both, it inflates memory.
ii.
Confusing BFS and DFS where order matters.
Shortest-path problems need BFS on an unweighted graph. DFS doesn't produce shortest paths — it commits to a direction and only backtracks on a dead end.
iii.
Recursion depth on DFS.
Recursive DFS over a 1000×1000 grid can overflow the call stack on a single long path. Switch to an explicit stack for large inputs, or use BFS where it works.
05 / Go practice — on LeetCode
Four problems. The first two are bread-and-butter flood-fill / reachability; the third pushes you into multi-source BFS; the fourth lifts the same algorithm onto an implicit graph.