Leetcode(286) Walls and Gates

发表于 | 分类于

Description

You are given a m x n 2D 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 value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

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:

Given the 2D grid:

1
2
3
4
INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

1
2
3
4
3  -1   0   1
2   2   1  -1
1  -1   2  -1
0  -1   3   4

解法

采用BFS解题即可。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class Solution {
    /**
     * @param rooms: m x n 2D grid
     * @return: nothing
     */
    public void wallsAndGates(int[][] rooms) {
        // write your code here
        if (rooms.length == 0) {
            return;
        }
        int[] dirx = {-1, 1, 0, 0};
        int[] diry = {0, 0, 1, -1};
        int[][] visit = new int[rooms.length][rooms[0].length];
        for (int i = 0; i < rooms.length; i++) {
            for (int j = 0; j < rooms[0].length; j++) {
                if (rooms[i][j] == 0) {
                    for (int a = 0; a < rooms.length; a++) {
                        for (int b = 0; b < rooms[0].length; b++) {
                            visit[a][b] = 0;
                        }
                    }
                    Queue<Node> q = new LinkedList<>();
                    q.offer(new Node(i, j));
                    int step = 0;
                    while (!q.isEmpty()) {
                        int size = q.size();
                        for (int k = 0; k < size; k++) {
                            Node now = q.poll();
                            int x = now.i;
                            int y = now.j;
                            rooms[x][y] = rooms[x][y] < step ? rooms[x][y] : step;
                            visit[x][y] = 1;
                            for (int l = 0; l < 4; l++) {
                                int nextx = x + dirx[l];
                                int nexty = y + diry[l];
                                if (nextx >= 0 && nextx < rooms.length && nexty >= 0 && nexty < rooms[0].length && rooms[nextx][nexty] != 0 && rooms[nextx][nexty] != -1 && visit[nextx][nexty] == 0) {
                                    q.offer(new Node(nextx, nexty));
                                }
                            }
                        }
                        step++;
                    }
                }
            }
        }
    }

    class Node {
        int i;
        int j;

        Node(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}