Distance to the nearest zero
You get a grid grid of 0s and 1s, written as a list of rows, with at least one 0 in it. From a cell you may step to the cell directly above, below, left or right of it, as long as that cell is inside the grid. Every cell can be stepped on, whether it holds a 0 or a 1.
Return a new grid of the same shape where each cell holds the fewest steps from that cell to any cell holding a 0. A cell that holds a 0 gets 0. Leave grid itself unchanged.
Picture a floor plan where every 0 is an exit: each cell wants to know how many steps away its nearest exit is.
grid = [[0, 1, 1], [1, 1, 1], [1, 1, 0]]Output[[0, 1, 2], [1, 2, 1], [2, 1, 0]]The center is 2 steps from both 0s. The top right corner is also 2 steps from both: two down, or two left.
grid = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]Output[[2, 1, 2], [1, 0, 1], [2, 1, 2]]Each corner needs one step up or down and one step sideways to reach the center.
grid = [[1, 0, 1, 1]]Output[[1, 0, 1, 2]]One row. The last cell is two steps right of the 0.
At least 1 row and 1 column, and every row has the same length.
rows × columns ≤ 104
Every cell is 0 or 1, and at least one cell is 0.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.