286. Walls and Gates
Problem
Fill each empty room with the distance to its nearest gate. Walls are -1, gates are 0, empty rooms are INF.
You are given a 2D grid where:
- -1 represents a wall
- 0 represents a gate
- INF (represented as some large value like 2^31-1) represents an empty room
Fill each empty room (INF) with the distance to its nearest gate. If a room cannot reach a gate, leave it as INF.
Examples
Input: [[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]]
Input: [[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]]
Hints
Use BFS starting from all gates simultaneously.
Track distance as you expand from each gate.
Only update if the current distance is smaller.
Related Problems
286. Walls and Gates
Fill each empty room with the distance to its nearest gate. Walls are -1, gates are 0, empty rooms are INF.