286 Walls and Gates

Search…
286 Walls and Gates
286. Walls and Gates
1. Question
You are given am x n2D grid initialized with these three possible values.
1.-1- A wall or an obstacle.
2.0- A gate.
3.INF- Infinity means an empty room. We use the value2^31- 1 = 2147483647to representINF
as you may assume that the distance to a gate is less than2147483647
Fill each empty room with the distance to itsnearestgate. If it is impossible to reach a gate, it should be filled withINF.
For example, given the 2D grid:
1
INF  -1  0  INF
2
INF INF INF  -1
3
INF  -1 INF  -1
4
  0  -1 INF INF
Copied!
After running your function, the 2D grid should be:
1
  3  -1   0   1
2
  2   2   1  -1
3
  1  -1   2  -1
4
  0  -1   3   4
Copied!
2. Implementation
(1) BFS
1
class Solution {
2
    public void wallsAndGates(int[][] rooms) {
3
        if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
4
            return;
5
        }
6
​
7
        int m = rooms.length, n = rooms[0].length;
8
        Queue<int[]> queue = new LinkedList<>();
9
​
10
        for (int i = 0; i < m; i++) {
11
            for (int j = 0; j < n; j++) {
12
                if (rooms[i][j] == 0) {
13
                    queue.add(new int[] {i, j});
14
                }
15
            }
16
        }
17
​
18
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
19
​
20
        while (!queue.isEmpty()) {
21
            int[] cell = queue.remove();
22
            int curRow = cell[0], curCol = cell[1];
23
​
24
            for (int[] direction : directions) {
25
                int nextRow = curRow + direction[0];
26
                int nextCol = curCol + direction[1];
27
​
28
                if (isValid(rooms, nextRow, nextCol)) {
29
                    rooms[nextRow][nextCol] = rooms[curRow][curCol] + 1;
30
                    queue.add(new int[] {nextRow, nextCol});
31
                }
32
            }
33
        }
34
    }
35
​
36
    public boolean isValid(int[][] matrix, int nextRow, int nextCol) {
37
        return nextRow >= 0 && nextRow < matrix.length && nextCol >= 0 && nextCol < matrix[0].length && matrix[nextRow][nextCol] == Integer.MAX_VALUE;
38
    }
39
}
Copied!
3. Time & Space Complexity
BFS: 时间复杂度O(mn), 空间复杂度O(mn)
279 Perfect Squares
317 Shortest Distance from All Buildings
Last modified 2yr ago
Copy link
Contents
286. Walls and Gates
1. Question
2. Implementation
3. Time & Space Complexity