661. Rooms and Exits
A warehouse floor is described by the grid rooms. A cell holding -1 is a solid wall, a cell holding 0 is a charging dock, and a cell holding any positive number is an empty bay whose distance has not been measured yet (the positive number itself carries no meaning). Robots move one step at a time up, down, left or right and can never enter a wall.
Return a new grid of the same shape in which every empty bay is replaced by the number of steps needed to reach the nearest charging dock. Walls and docks keep their values, and a bay that no dock can reach becomes -2. The input grid must not be modified. Aim for time and extra space proportional to the number of cells, which matters because the floor can hold tens of thousands of bays and many of them share the same closest dock.
Example 1
- Input:
- rooms = [[0,100000,100000,100000],[100000,-1,-1,100000],[100000,100000,100000,0]]
- Output:
- [[0,1,2,2],[1,-1,-1,1],[2,2,1,0]]
- Explanation:
Every bay is at most 2 steps from one of the two docks, for example the top-right bay is 2 steps from the bottom-right dock, so the result is [[0,1,2,2],[1,-1,-1,1],[2,2,1,0]].
Example 2
- Input:
- rooms = [[7,-1,0],[3,-1,5],[9,-1,1]]
- Output:
- [[-2,-1,0],[-2,-1,1],[-2,-1,2]]
- Explanation:
The wall column splits the floor: the right side gets distances 1 and 2, while the left column cannot reach any dock and becomes -2.
Constraints
1 ≤ rows, cols ≤ 300
each cell is -1, 0, or an integer in [1, 100000]
the grid may contain no docks at all
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 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(rows*cols)
- Space
- O(rows*cols)