Walls and Gates
MediumGraphs
You are given an m x n grid rooms where each cell is one of:
-1: a wall0: a gate2147483647: an empty room (this value stands for infinity,2^31 - 1)
Fill each empty room with the number of steps to its nearest gate. A step moves to a neighbouring cell up, down, left, or right; you can walk through gates and empty rooms but not through walls. If an empty room cannot reach any gate, leave it as 2147483647. Walls and gates keep their values.
Return the updated grid. You may modify rooms in place and return it.
Example 1
- Input:
- rooms = [[2147483647, 2147483647, 0, 2147483647], [2147483647, -1, -1, 2147483647], [0, 2147483647, 2147483647, 2147483647]]
- Output:
- [[2, 1, 0, 1], [1, -1, -1, 2], [0, 1, 2, 3]]
- Explanation
- Each room takes the distance to whichever gate is closer. For example, row 2, column 2 is 2 steps from the bottom-left gate but 4 steps from the top gate (the walls force a detour along the right side), so it becomes 2.
Example 2
- Input:
- rooms = [[0, -1, 2147483647], [-1, 2147483647, 2147483647]]
- Output:
- [[0, -1, 2147483647], [-1, 2147483647, 2147483647]]
- Explanation
- The gate is boxed in by walls, so none of the three rooms can reach it and they all stay
2147483647.
Example 3
- Input:
- rooms = [[2147483647, 0, 2147483647, 2147483647, 0]]
- Output:
- [[1, 0, 1, 1, 0]]
- Explanation
- Row with two gates: the room at column 3 is one step from the gate at column 4, closer than the 2 steps to column 1.
Constraints
m == rooms.length,n == rooms[i].length- 1 ≤
m,n≤ 250 rooms[i][j]is-1,0, or2147483647