Given a 2D grid with INF (empty room), -1 (wall), 0 (gate), fill each empty room with the distance to its nearest gate. If impossible, leave as INF.
Input: [[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]] → Fill distances from gates
Multi-source BFS starting from all gates (0-valued cells) simultaneously. Each BFS level adds 1 to the distance.
- Add all gate positions (value==0) to BFS queue.
- BFS outward: for each current cell, try 4 neighbors.
- If neighbor is INF (unvisited room): set dist = current+1, add to queue.
- Walls (-1) are skipped.
import java.util.*;
class Solution {
public void wallsAndGates(int[][] rooms) {
int m = rooms.length, n = rooms[0].length;
Queue<int[]> q = new LinkedList<>();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (rooms[i][j] == 0) q.offer(new int[]{i,j});
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int[] d : dirs) {
int r = cur[0]+d[0], c = cur[1]+d[1];
if (r>=0 && r<m && c>=0 && c<n && rooms[r][c] == Integer.MAX_VALUE) {
rooms[r][c] = rooms[cur[0]][cur[1]] + 1;
q.offer(new int[]{r,c});
}
}
}
}
}
- Time Complexity: O(M*N)
- Space Complexity: O(M*N)