Walls and Gates
Part of Practice: BFS Waves
You get a grid (up to 250×250) where each cell is one of three things: -1 (a wall), 0 (a gate), or INF = 2147483647 (an empty room). Fill every empty room, in place, with the number of steps to its nearest gate, moving up/down/left/right and never through walls. A room that cannot reach any gate keeps the value INF.
Examples
- Input:
- rooms = [[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]] (INF = 2147483647)
- Output:
- [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
Each empty room now holds the walking distance to whichever gate is closest. For example the top-left room reaches the gate at (3,0) in 3 steps going down the left column.
- Input:
- rooms = [[INF]]
- Output:
- [[2147483647]]
One empty room and no gates — it stays INF because no gate is reachable.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.