655. Distance to Nearest Zero
A sensor field is stored as a matrix grid of 0 and 1. A cell with 0 is a working beacon; a cell with 1 is a plain tile. Moving from a cell to the cell directly above, below, left or right costs one step, and you may walk through any cell.
Return a matrix of the same size in which each cell holds the minimum number of steps needed to reach a beacon from that cell. A beacon cell has distance 0. If the whole matrix has no beacon at all, every answer cell must be -1. Aim for O(R * C) time and O(R * C) extra space; running a separate search from every cell is too slow for the largest inputs.
Example 1
- Input:
- grid = [[0,1,1,0],[1,1,1,1],[1,1,1,0]]
- Output:
- [[0,1,1,0],[1,2,2,1],[2,2,1,0]]
- Explanation:
Every 1 is measured to its closest 0: the cells in the middle row are one or two steps away.
Example 2
- Input:
- grid = [[1,1,1],[1,1,1]]
- Output:
- [[-1,-1,-1],[-1,-1,-1]]
- Explanation:
There is no 0 anywhere, so every cell gets -1.
Example 3
- Input:
- grid = [[1,1,1,1],[1,0,1,1],[1,1,1,1]]
- Output:
- [[2,1,2,3],[1,0,1,2],[2,1,2,3]]
- Explanation:
Distances grow with the number of up/down/left/right steps from the single 0.
Constraints
1 ≤ R, C ≤ 400
grid[i][j] is 0 or 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(R * C)
- Space
- O(R * C)