Pattern #14
Grid & Graph BFS
EssentialShortest paths in unweighted graphs and multi-source floods on grids.
When to use
Every edge costs the same (or each grid step is one move). You need distance, reachability, or connected components via flood fill.
Recognition cues
- Shortest path in a grid / word ladder
- Number of islands / rotting oranges
- Multi-source BFS from all gates or rotting cells
Common pitfalls
- Not marking visited when enqueueing (duplicates explode)
- 4-dir vs 8-dir inconsistency with the problem
- Using DFS when shortest path is required
90-second recognition drill
Which pattern fits best?
- Shortest path in a grid / word ladder
- Number of islands / rotting oranges
- Multi-source BFS from all gates or rotting cells
Interactive
Mental model
A full worked walkthrough of the invariant. Pause, scrub the dots, or use ← →. Aim to narrate each step yourself.
queue = [S] · dist[S] = 0
Grid BFS: treat each cell as a node; 4-neighbors are edges. Seed the queue at the start.
How to think about it
BFS explores level by level. The mental model draws grids and free graphs (adjacency) so you see nodes, edges, and distances. The first time you reach a node is the shortest number of edges. On grids, neighbors are up/down/left/right. Multi-source BFS seeds the queue with all starts at distance 0.
Template shapes
| Shape | Core move | Notes |
|---|---|---|
| Single source | Queue + dist map | First reach wins |
| Multi-source | Enqueue all sources | Same expansion |
| Components | Flood each unvisited | Count islands |
Complexity baseline
O(V+E) (or O(R·C) on a grid). Space O(V) for queue and visited.
From template to problem
- Define neighbors and valid cell predicate.
- Initialize queue and visited (or dist) from source(s).
- While queue: pop, expand unused neighbors, record dist.
- Stop early if target found; else return counts/distances.
Template
Same skeleton in TypeScript, Python, and C#. Adapt the invariant; keep the structure.
/** Grid BFS template: multi-source flood from all zeros (dist fill). */
export function wallsAndGatesTemplate(rooms: number[][]): void {
const m = rooms.length, n = rooms[0]?.length ?? 0;
const q: [number, number][] = [];
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (rooms[r]![c] === 0) q.push([r, c]);
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
while (q.length) {
const [r, c] = q.shift()!;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
if (rooms[nr]![nc] !== 2147483647) continue;
rooms[nr]![nc] = rooms[r]![c]! + 1;
q.push([nr, nc]);
}
}
}
/** Grid BFS template: multi-source flood from all zeros (dist fill). */
export function wallsAndGatesTemplate(rooms: number[][]): void {
const m = rooms.length, n = rooms[0]?.length ?? 0;
const q: [number, number][] = [];
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (rooms[r]![c] === 0) q.push([r, c]);
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
while (q.length) {
const [r, c] = q.shift()!;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
if (rooms[nr]![nc] !== 2147483647) continue;
rooms[nr]![nc] = rooms[r]![c]! + 1;
q.push([nr, nc]);
}
}
}
- 1#127 Word LadderGuidehard
- 2#200 Number of IslandsGuidemedium
- 3#286 Walls and GatesGuidemedium
- 4#542 01 MatrixGuidemedium
- 5#752 Open the LockGuidemedium
- 6#994 Rotting OrangesGuidemedium