253. Walls and Gates
You are given an m x n grid rooms in which every cell holds one of three values:
-1— a wall that can never be entered,0— a gate,2147483647— an empty room (the value is the largest 32-bit integer, standing in for "infinity").
Fill every empty room with the number of steps to its nearest gate, moving one cell up, down, left, or right at a time and never through walls, and return the grid. If a room cannot reach any gate, it keeps the value 2147483647. Gates and walls keep their original values.
One search per room is the slow way — think about where a single search could start instead.
Example 1:
Input: rooms = [[INF, -1, 0, INF], [INF, INF, INF, -1], [INF, -1, INF, -1], [0, -1, INF, INF]]
Output: [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]
Explanation: Each empty room now shows its walking distance to the closest of the two gates; walls and gates are untouched.
Example 2:
Input: rooms = [[0, INF, INF]]
Output: [[0, 1, 2]]
Explanation: A single row: the rooms sit one and two steps from the only gate.
Constraints:
- 1 ≤ m, n ≤ 200
- rooms[i][j] is -1, 0, or 2147483647.
Hints:
Launching a fresh search from every empty room repeats the same flood over and over. Reverse the direction: the distance from a room to its nearest gate equals the distance from the nearest gate to that room.
Seed one queue with every gate at distance 0 and run a single BFS. Because all sources start together, the first wave to touch an empty room is guaranteed to carry its true shortest distance — write it once and never revisit that cell.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: rooms = [[INF, -1, 0, INF], [INF, INF, INF, -1], [INF, -1, INF, -1], [0, -1, INF, INF]]
Expected output: [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]