409. 01 Matrix
You are given an m × n grid mat whose cells hold only 0s and 1s. For every cell, work out the length of the shortest walk to a cell containing a 0, where each step moves one cell up, down, left, or right.
Return a grid of the same shape holding those distances. Cells that already contain a 0 get distance 0. At least one 0 is guaranteed to exist, so every answer is finite.
Example 1:
Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
Explanation: The center 1 touches a 0 directly above, so its distance is 1. The bottom-middle cell must take two steps (up, then up again, or up then sideways) to reach any 0.
Example 2:
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
Explanation: Only the center holds a 1, and every neighbor of it is a 0 — one step away.
Constraints:
- 1 ≤ m, n ≤ 100
- mat[i][j] is 0 or 1
- At least one cell of mat contains a 0
Hints:
Searching from each 1 outward repeats an enormous amount of work. What if the search ran from the 0s instead?
Drop every 0 into a BFS queue at distance 0 before the search starts. A breadth-first wave from all of them at once labels each cell with its true nearest-zero distance the first time the wave touches it.
A pure DP alternative: one pass top-left → bottom-right using the up/left neighbors, then one pass back using the down/right neighbors. Together the two passes cover all four step directions.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Expected output: [[0,0,0],[0,1,0],[1,2,1]]