Fill each empty room (INF) in a matrix with the distance to its nearest gate (0). Walls are -1.
Multi-source BFS from all gates simultaneously
Multi-source BFS starting from all gate (0) positions. Each BFS level adds 1 to the distance.
- Enqueue all gate positions.
- BFS: for each cell, update 4-directional INF neighbors with distance+1.
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)