Distance of Nearest Cell Having 1 (01 Matrix)
WHAT IT SAYS
For every cell of a binary grid, compute the distance to the nearest cell containing a 1.
WHAT IT'S REALLY ASKING
"Asked from each 0, 'where is my nearest 1?' is a search per cell — expensive and repetitive. Flip the question: let all the 1s ask, in unison, 'when do I reach each 0?' One wave expanding from every 1 simultaneously stamps each cell, on first touch, with exactly the answer the original question wanted. Same numbers, one traversal instead of thousands."
BFS outward from every 0
O((mn)^2) worst case — a full expansion per zero cellFor each cell containing a 0, run a fresh BFS expanding in rings until any 1 is found; record the ring number as that cell's answer. Cells with 1 answer zero trivially.
WHERE THE WORK IS WASTED — Adjacent zeros run nearly identical searches: their expansion rings overlap almost completely, and each re-explores territory its neighbour's search just mapped — the answers even differ by at most 1 between adjacent cells, screaming that the computations are entangled, yet each BFS starts amnesiac. On a grid with one lone 1 in the corner, every one of the mn-1 zeros floods most of the grid to find it: quadratic re-discovery of a single landmark. The per-source framing multiplies the cost by the number of askers when all the askers want distances to the same target set.
Nearest-1 distance is arrival time from all the 1s.
The inversion, stated as an identity: for any cell c, min over all 1-cells s of dist(c, s) — the question as posed — equals the time at which a unit-speed wave launched simultaneously from ALL 1-cells first touches c. Grid distance is symmetric, so dist(c, s) = dist(s, c), and the minimum over sources is exactly what the earliest-arriving wavefront computes. The per-0 question ('find my nearest 1') and the from-all-1s question ('stamp everything I reach') have identical answers — but wildly different costs, because the second is ONE multi-source BFS. Mechanically this is the rotting-oranges engine — seed the queue with every 1 at distance 0, expand in levels, stamp each cell on FIRST touch (first touch is minimal distance, by BFS's level-order guarantee) — but the lesson here is different and more general: it is the inversion itself. When MANY askers query distance to the NEAREST member of a target set, never search per asker; propagate once from the whole target set. The number of sources is irrelevant to BFS's cost — the queue just starts fuller — while the per-asker version pays per asker. Why the direction flip is free: unweighted grids have symmetric distances. That symmetry is load-bearing — on a DIRECTED graph (one-way streets), inverting the question requires reversing every edge first, and on weighted graphs the multi-source trick still works but the engine becomes Dijkstra with a pre-seeded heap. The visited discipline: stamp-and-enqueue on first touch, and never re-enqueue — every cell enters the queue exactly once, so the whole grid costs one read. The output array itself can serve as the visited marker (initialise to a sentinel, stamped = visited), the flood-fill economy reappearing.
Seed all 1s at zero, expand, stamp on first touch
O(m·n) time — each cell enqueued once — O(m·n) queue worst caseInitialise dist[][] to -1 (unvisited); enqueue every 1-cell with dist 0. BFS: pop, for each in-bounds 4-neighbour with dist == -1, set its dist to popped's dist + 1 and enqueue. The dist array at the end is the answer, and it doubled as the visited set throughout.
Propagate From the Targets
YOU'LL SEE IT AGAIN WHEN
- Many cells each ask for distance to the nearest member of a common target set — per-asker searches would overlap almost entirely.
- Distances are symmetric (undirected, unweighted), so 'to nearest target' equals 'from all targets, first arrival' for free.
- The output array can be initialised to a sentinel and double as the visited structure — stamped means done.