public class Solution {

public void wallsAndGates(int[][] rooms) {

```
//Algo thinking: revser thinking, from gate to room; BFS
//time = O(N*M), space = O(N*M)
if (rooms == null || rooms.length == 0) return;
int n = rooms.length;
int m = rooms[0].length;
int wall = -1, gate = 0, room = Integer.MAX_VALUE;
// step1: find all gates
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (rooms[i][j] == gate) {
queue.add(new int[]{i, j});
}
}
}
// step2: BFS
int[][] dir = new int[][]{{1, 0},{-1, 0},{0, 1},{0, -1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d: dir) {
int i = cell[0] + d[0];
int j = cell[1] + d[1];
if (i < 0 || j < 0 || i >= n || j >= m || rooms[i][j] != room) continue;
rooms[i][j] = rooms[cell[0]][cell[1]] + 1;
queue.offer(new int[]{i, j});
}
}
}
```

}