Matrix as Graph

Shortest paths and distances in a grid: BFS from one cell, BFS from many cells at once, counting levels as time, and the deque trick for steps that cost 0 or 1.

Overview

A grid is a graph you never have to build. Each cell is a node, and its neighbors are the cells next to it. The Island Traversal topic uses that view to count regions, where DFS and BFS both work. This topic covers the questions where only BFS gives the right answer: fewest steps to a target, the distance from every cell to the nearest special cell, and how long something takes to spread.

The cell is the node

The neighbors of the cell in row r and column c are computed from r and c, and any that fall off the grid are skipped. Ask which moves count: four directions (sharing an edge) is the default, eight (sharing an edge or a corner) is used by Shortest Path in Binary Matrix.

Up — (r - 1, c) — r > 0
Down — (r + 1, c) — r 0
Right — (r, c + 1) — c < cols - 1
Diagonals (8-way only) — (r ± 1, c ± 1) — Both coordinates in range

A grid with R rows and C columns has R × C nodes. With four-way moves it has R(C - 1) horizontal edges and C(R - 1) vertical ones, which is 2RC - R - C in total: 12 for a 3 × 3 grid, 31 for 4 × 5. A traversal touches each cell and each edge a constant number of times, so it is O(R × C).

Why BFS and not DFS

DFS finds a path; BFS finds the shortest one. BFS takes cells from a queue in the order they were added, so every cell at distance d is handled before any cell at distance d + 1, and the first time a cell is reached is along a shortest route. DFS commits to one direction and can reach the target by a long detour first.

Marking on entry matters more in grids than elsewhere, because an open cell has up to four (or eight) neighbors that can all try to add it.

One source: Shortest Path in Binary Matrix

The task is the shortest path of 0 cells from the top-left to the bottom-right corner, moving in eight directions, where the length is the number of cells visited. So the source starts at distance 1, not 0, and the answer is the distance of the bottom-right cell, or -1 if the queue empties first. If either corner is a 1, the answer is -1 before any search.

Trace on the grid below, which has open cells along the top row and the right column.

row 0 — 0 — 0 — 0
row 1 — 1 — 1 — 0
row 2 — 1 — 1 — 0

1 — (0, 0) — 1 — (0, 1) at 2 — (0, 1)
2 — (0, 1) — 2 — (0, 2) at 3, (1, 2) at 3 — (0, 2), (1, 2)
3 — (0, 2) — 3 — none — (1, 2)
4 — (1, 2) — 3 — (2, 2) at 4 — (2, 2)
5 — (2, 2) — 4 — target reached

The answer is 4: the diagonal step from (0, 1) to (1, 2) saves a move. You can return as soon as the target is taken out of the queue, or as soon as it is marked; both give the same distance.

Many sources at once: 01 Matrix

01 Matrix asks, for every cell, the distance to the nearest 0. Running a BFS from each 1 costs O(R × C) per cell, which is O((R × C)²) in total: 10⁸ steps for a 100 × 100 grid.

Instead, turn it around: put every 0 cell in the queue at distance 0 and run one BFS. When the wavefronts from different zeros meet, each cell has already been marked by the zero closest to it, because a nearer zero's wavefront arrives first. One BFS, each cell queued once: O(R × C).

row 0 — 0 — 1 — 1
row 1 — 1 — 1 — 1
row 2 — 1 — 1 — 0

0 — (0, 0), (2, 2), the seeds — 0 . . / . . . / . . 0
1 — (1, 0), (0, 1), (1, 2), (2, 1) — 0 1 . / 1 . 1 / . 1 0
2 — (2, 0), (1, 1), (0, 2) — 0 1 2 / 1 2 1 / 2 1 0

The center cell is two steps from either zero and is marked once, at level 2, by whichever wavefront reaches it first in the queue order.

Multi-source BFS is single-source BFS with a longer starting queue. Nothing else changes, and the cost does not grow with the number of sources.

Levels as time: Rotting Oranges

Rotting Oranges is multi-source BFS where each level is one minute. Every fresh orange next to a rotten one rots in the next minute, so the rotten oranges are the sources and the answer is the number of levels needed to reach every fresh orange.

Process the queue one level at a time: note the queue length, take exactly that many cells, and count one minute per level that rots at least one orange. Also count the fresh oranges at the start and subtract as they rot; if any are left when the queue empties, return -1.

row 0 — 2 — 1 — 0
row 1 — 1 — 1 — 1
row 2 — 0 — 0 — 1

0 — the source (0, 0) — 5
1 — (1, 0), (0, 1) — 3
2 — (1, 1) — 2
3 — (1, 2) — 1
4 — (2, 2) — 0

The answer is 4. Two edge cases catch people: a grid with no fresh orange answers 0 without any BFS, and a level that rots nothing must not add a minute, which is why the loop condition checks that fresh oranges remain.

Rotting Oranges — Rotten oranges — One minute
01 Matrix — Every 0 — One more step from the nearest 0
Fire spreading, flood — Every burning or flooded cell — One time step

Stopping on a condition: Nearest Exit

Nearest Exit from Entrance in Maze asks for the fewest steps from the entrance to any open cell on the border, and the entrance itself does not count as an exit. That last rule is the trap: an entrance on the border is not an answer of 0.

The BFS is plain single-source BFS with one change: check the exit condition when a cell is reached, not when it is taken out, and skip the check for the entrance. Return the distance of the first border cell reached; return -1 if the queue empties.

(1, 1) in a 3 × 4 maze — no — no — keep searching
(0, 3) — yes — no — yes, return its distance
(0, 0), when it is the entrance — yes — yes — no

Two phases: Shortest Bridge

Shortest Bridge has exactly two islands of 1s and asks for the fewest 0 cells to flip to join them. The answer is the number of water cells on the shortest route between the two islands, and finding it takes two phases.

The DFS marks the first island with a different value (2) so the BFS can tell it apart from the second island. The BFS then expands from all its cells at once. The moment a neighbor holds a 1 that is not painted, the second island is reached, and the number of levels completed so far is the number of water cells to flip.

1 — (1, 0), (0, 1)
2 — (2, 0), (1, 1), (0, 2)
3 — (2, 1), (1, 2)
next — (2, 2) is land: answer 3

Steps that cost 0 or 1

BFS assumes every step costs the same. When some steps are free and others cost 1, for example following a signpost costs 0 and changing it costs 1 in Minimum Cost to Make at Least One Valid Path in a Grid, use a deque instead of a queue. A neighbor reached at cost 0 goes to the front (it belongs to the current level), and a neighbor reached at cost 1 goes to the back. The deque stays sorted by cost, so the first time a cell is taken out is at its lowest cost. This is 0-1 BFS, and it keeps the O(R × C) bound. In Python, collections.deque appends and pops at either end in O(1).

All equal — BFS — Queue — O(R × C)
0 or 1 — 0-1 BFS — Deque: cost 0 to the front, cost 1 to the back — O(R × C)
Any non-negative — Dijkstra — Min-heap keyed by cost — O(R × C log(R × C))

What you will be able to do

Treat a grid as a graph without building one, and say why a traversal is O(R × C).
Explain why BFS, not DFS, gives fewest steps, and why cells are marked when they enter the queue.
Seed a BFS with many sources to get every cell's distance to the nearest source in one pass.
Count BFS levels as minutes or layers, and handle the off-by-one and the -1 cases.
Choose between BFS, 0-1 BFS and Dijkstra from what a step costs.

When to use it

Fewest steps from one cell to a target, possibly with eight-way moves (Shortest Path in Binary Matrix)
The distance from every cell to the nearest cell of a kind (01 Matrix)
Something spreading one step per time unit from several places (Rotting Oranges)
The nearest cell that meets a condition, such as a border cell (Nearest Exit)
The fewest cells to flip between two regions (Shortest Bridge)
Steps that cost 0 or 1 (0-1 BFS), or varied non-negative costs (Dijkstra on the grid)

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio