Walls and Gates
Medium · graph traversal
You are given a floor plan as a rectangular grid of integers, rooms. Each cell holds one of three values:
-1is a wall. You cannot enter it.0is a gate.2147483647is an empty room. This value is just a stand-in for "no distance known yet".
From any cell you can walk to the cell directly above, below, left or right of it, as long as that cell is not a wall. Each such move is one step.
Fill in every empty room with the number of steps from it to its nearest gate. If no gate can be reached from a room, leave it as 2147483647. Walls and gates stay as they are.
Return the filled grid. You may change rooms in place and return it.
Examples
Example 1
Input: rooms = [[0, 2147483647, 2147483647], [2147483647, -1, 2147483647], [2147483647, 2147483647, 0]]
Output: [[0, 1, 2], [1, -1, 1], [2, 1, 0]]
The top-right room is two steps from either gate. The wall in the middle is left alone.
Example 2
Input: rooms = [[0, -1, 2147483647], [2147483647, -1, 2147483647]]
Output: [[0, -1, 2147483647], [1, -1, 2147483647]]
The wall column cuts off the right-hand rooms from the gate, so they keep the stand-in value.
Constraints
- 1 <= rows, cols <= 25
- Every cell is -1, 0 or 2147483647.
- All rows have the same length.