101
0/320
Loading content...
You are given an m × n binary grid called mat, where each cell contains either a 0 or a 1. Your task is to compute a new matrix of the same dimensions where each cell contains the Manhattan distance to the nearest cell with value 0 in the original grid.
The Manhattan distance (also known as taxicab distance) between two cells sharing a common horizontal or vertical edge is exactly 1. More formally, the distance between cell (r1, c1) and cell (r2, c2) is calculated as |r1 - r2| + |c1 - c2|.
For cells that already contain 0, the distance is naturally 0 since they are the target themselves. For cells containing 1, you must find the shortest path (measured in cell steps) to any cell containing 0.
The grid is guaranteed to contain at least one cell with value 0, ensuring that a valid distance can always be computed for every cell.
mat = [[0,0,0],[0,1,0],[0,0,0]][[0,0,0],[0,1,0],[0,0,0]]The center cell (1,1) contains a 1. Its nearest 0 is any of its four adjacent neighbors, so the distance is 1. All other cells already contain 0, so their distances are 0.
mat = [[0,0,0],[0,1,0],[1,1,1]][[0,0,0],[0,1,0],[1,2,1]]The bottom-left cell (2,0) has its nearest 0 at (1,0), distance = 1. The bottom-middle cell (2,1) has its nearest 0 at either (0,1) or (1,0) or (1,2), with the shortest path being 2 steps. The bottom-right cell (2,2) has its nearest 0 at (1,2), distance = 1. The center cell (1,1) has its nearest 0 at any of its adjacent neighbors except (2,1).
mat = [[0,1],[1,1]][[0,1],[1,2]]Starting from the only 0 at position (0,0): cell (0,1) is 1 step away, cell (1,0) is 1 step away, and cell (1,1) is 2 steps away (must traverse through either (0,1) or (1,0) to reach it).
Constraints