Back to DSA
Walls and Gates
mediumAn m-by-n grid contains walls (-1), target locations (0), and open spaces (marked with a large sentinel value). Replace each open space's value with the shortest distance to any target. Leave walls and unreachable spaces unchanged.
Examples
Example 1:
Input:
rooms = [[2147483647,0,2147483647],[2147483647,-1,2147483647],[2147483647,2147483647,0]]Output:
[[1,0,1],[2,-1,1],[3,2,0]]Explanation: Each open space is filled with its shortest distance to a target location.
Hints
import java.util.*;
class Solution {
public void wallsAndGates(int[][] rooms) {
int m = rooms.length, n = rooms[0].length;
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (rooms[i][j] == 0) queue.offer(new int[]{i, j});
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] == Integer.MAX_VALUE) {
rooms[nr][nc] = rooms[cell[0]][cell[1]] + 1;
queue.offer(new int[]{nr, nc});
}
}
}
}
}Time complexity
O(m * n)Space complexity
O(m * n)