Mid/Senior
Walls and Gates
You are given an m x n grid rooms initialized with three possible values:
-1represents a wall or obstacle.0represents a gate.2^31 - 1represents an empty room.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, the room should remain 2^31 - 1.
The distance between two adjacent cells is 1, and movement is allowed only up, down, left, or right.
You must modify rooms in-place and return nothing.
Example 1
2147483647 -1 0 2147483647
2147483647 2147483647 2147483647 -1
2147483647 -1 2147483647 -1
0 -1 2147483647 2147483647Input
rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]Output
[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]Each empty room is filled with the shortest distance to the nearest gate while walls remain unchanged.
Example 2
-1
Input
rooms = [[-1]]Output
[[-1]]The wall is unchanged because it is not an empty room.
Constraints
- m == rooms.length
- n == rooms[i].length
- 1 <= m, n <= 250
- rooms[i][j] is -1, 0, or 2^31 - 1