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 / 61
visited
0
frontier
1
current
—
0 / 61
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
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.
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.
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
medium32
01Word Search— LC 79→02Surrounded Regions— LC 130→03Clone Graph— LC 133→04Number of Islands— LC 200→05Course Schedule— LC 207→06Course Schedule II— LC 210→07Graph Valid Tree— LC 261→08Walls and Gates— LC 286→09Number of Connected Components in an Undirected Graph— LC 323→10Evaluate Division— LC 399→11Pacific Atlantic Water Flow— LC 417→12Minimum Genetic Mutation— LC 433→1301 Matrix— LC 542→14Number of Provinces— LC 547→15Max Area of Island— LC 695→16Open the Lock— LC 752→17Is Graph Bipartite?— LC 785→18All Paths From Source to Target— LC 797→19Keys and Rooms— LC 841→20Possible Bipartition— LC 886→21Snakes and Ladders— LC 909→22Shortest Bridge— LC 934→23Rotting Oranges— LC 994→24Number of Enclaves— LC 1020→25Shortest Path in Binary Matrix— LC 1091→26Shortest Path with Alternating Colors— LC 1129→27As Far from Land as Possible— LC 1162→28Path with Maximum Gold— LC 1219→29Number of Closed Islands— LC 1254→30Number of Operations to Make Network Connected— LC 1319→31Count Sub Islands— LC 1905→32Maximum Number of Fish in a Grid— LC 2658→
hard11
01Word Ladder II— LC 126→02Word Ladder— LC 127→03Word Search II— LC 212→04Number of Islands II— LC 305→05Longest Increasing Path in a Matrix— LC 329→06Reconstruct Itinerary— LC 332→07Robot Room Cleaner— LC 489→08Bus Routes— LC 815→09Making A Large Island— LC 827→10Unique Paths III— LC 980→11Shortest Path in a Grid with Obstacles Elimination— LC 1293→