0286. Walls and Gates
https://leetcode.com/problems/walls-and-gates
Description
You are given an m x n
grid rooms
initialized with these three possible values.
-1
A wall or an obstacle.0
A gate.INF
Infinity means an empty room. We use the value231 - 1 = 2147483647
to representINF
as you may assume that the distance to a gate is less than2147483647
.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF
.
Example 1:

**Input:** rooms = [[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]]
Example 2:
**Input:** rooms = [[-1]]
**Output:** [[-1]]
Example 3:
**Input:** rooms = [[2147483647]]
**Output:** [[2147483647]]
Example 4:
**Input:** rooms = [[0]]
**Output:** [[0]]
Constraints:
m == rooms.length
n == rooms[i].length
1 <= m, n <= 250
rooms[i][j]
is-1
,0
, or231 - 1
.
ac1: BFS
class Solution {
public void wallsAndGates(int[][] rooms) {
// edge case
if (rooms.length == 0 || rooms[0].length == 0) return;
Queue<int[]> q = new LinkedList<int[]>();
int row = rooms.length;
int col = rooms[0].length;
// walk, get gates
for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (rooms[r][c] == 0) q.offer(new int[] {r, c});
}
}
// BFS
int layer = 0;
while (!q.isEmpty()) {
layer++;
int len = q.size();
for (int i = 0; i < len; i++) {
int[] head = q.poll();
int r = head[0]; int c = head[1];
if (r < row-1 && rooms[r+1][c] > layer) {
rooms[r+1][c] = layer;
q.offer(new int[] {r+1, c});
}
if (r > 0 && rooms[r-1][c] > layer) {
rooms[r-1][c] = layer;
q.offer(new int[] {r-1, c});
}
if (c < col-1 && rooms[r][c+1] > layer){
rooms[r][c+1] = layer;
q.offer(new int[] {r, c+1});
}
if (c > 0 && rooms[r][c-1] > layer) {
rooms[r][c-1] = layer;
q.offer(new int[] {r, c-1});
}
}
}
}
}
/**
walk, get 0s
BFS, if val > layer, set val = layer, offer to queue
**/
Last updated
Was this helpful?