286. Distance of Nearest Cell Having 1 in a Binary Matrix

Given an R x C binary matrix containing at least one 1, for every cell find the Manhattan (grid-step, up/down/left/right only) distance to the nearest cell containing a 1. Print the resulting R x C matrix of distances, one row per line, space-separated.

Input: The first line contains two integers R and C, the matrix's dimensions. Each of the next R lines contains C space-separated 0/1 integers, one row of the binary matrix. Output: Print R lines, each with C space-separated integers - the Manhattan distance from each cell to the nearest cell containing a 1.

1 <= R, C <= 500

Seeding the BFS queue with ALL the 1-cells at once (not running one BFS per 1, and not running one BFS per 0) is the single key insight that turns an expensive repeated-search problem into one clean linear pass.

In a grid of 0s and 1s, figure out, for every single cell, how many grid-steps away the CLOSEST 1 is. Brute force: For every single 0-cell, run its OWN separate BFS or scan looking for the nearest 1 - this technically works, but with R*C total cells, running a full search from EACH one costs far too much (potentially O((R*C)²) in the worst case), extremely slow for large grids. Optimised: Multi-source BFS flips the direction of the search: instead of searching FROM every 0 looking for a 1, it searches FROM every 1 simultaneously, spreading outward together - since all the 1s start the race at the same time (distance 0), the first wave to reach any given 0-cell is guaranteed to have come from whichever 1 is genuinely closest, computed in one single combined pass over the whole grid.

For every cell in the matrix, scan every other cell that contains a 1 and compute the Manhattan distance to it, keeping the minimum. This directly computes the correct nearest distance for each cell by exhaustive comparison, but comparing every cell against every 1-cell is extremely wasteful when the matrix is large. Time: O((R*C)^2) Space: O(1)

Push every cell that already contains a 1 into a queue simultaneously, all at distance 0, then run a standard BFS: repeatedly pop a cell, and for each of its four unvisited neighbors, set its distance to one more than the current cell's and push it onto the queue. Because BFS explores in order of increasing distance and all sources start together, the first time any cell is reached is guaranteed to be via its nearest 1, so each cell's distance is finalized in a single, easy-to-reason-about pass with no directional bookkeeping. Time: O(R * C) Space: O(R * C)

Initialize dist[i][j] to 0 if the cell is 1 and infinity otherwise. In a first pass over the grid from top-left to bottom-right, update each cell's distance using the already-processed neighbors above and to the left: dist[i][j] = min(dist[i][j], dist[i-1][j]+1, dist[i][j-1]+1). In a second pass from bottom-right to top-left, do the same using the neighbors below and to the right. Combining both passes accounts for a nearest 1 lying in any of the four directions, computing the true answer without exhaustively comparing all cell pairs. Time: O(R * C) Space: O(R * C)

1. Instead of running a separate search from every single 0-cell (which would be slow), start a SINGLE combined breadth-first search that begins simultaneously from ALL the 1-cells at once, each with a starting distance of 0. 2. Expand outward one grid-step at a time in all four directions (up, down, left, right), level by level. 3. Because BFS naturally explores cells in order of increasing distance, the very FIRST time you reach any given cell is guaranteed to be via the shortest possible path to it. 4. Record that discovery distance for every cell as the BFS expands, and once every cell has been reached, you have your complete answer grid.

Time: O(R * C) - proportional to the total number of cells, since multi-source BFS visits every cell exactly once regardless of how many 1s or 0s there are. Space: O(R * C), for the BFS queue and the distance-tracking grid.

a matrix that is entirely 1s (every distance is 0); the largest allowed size R = C = 500 to confirm the multi-source BFS is efficient enough; a single row or single column (R = 1 or C = 1).

'Multi-source BFS' (seeding the queue with MULTIPLE starting points at once, all at distance 0) is a genuinely important, reusable pattern beyond just this problem - be ready to recognize when a problem is really asking for 'nearest distance to ANY of several targets', which is exactly this pattern's signature use case.