[LintCode] Problem 663 - Walls and Gates

Posted on | In ,

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 2^31 - 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 ROOM, that room should remain filled with INF

Example

No.1

Input:
[[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]]

Explanation:
the 2D grid is:

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

the answer is:

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

No.2

Input:
[[0,-1],[2147483647,2147483647]]

Output:
[[0,-1],[1,2]]

Code

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
public void wallsAndGates(int[][] rooms) {
    if (rooms == null || rooms.length == 0 || rooms[0].length == 0)
        return;
        
    int m = rooms.length;
    int n = rooms[0].length;
    int[][] directions = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    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});
        }
    }

    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            int[] pos = queue.poll();

            for (int[] direction : directions) {
                int x = direction[0] + pos[0];
                int y = direction[1] + pos[1];

                if (x < 0 || y < 0 || x >= m || y >= n || rooms[x][y] != Integer.MAX_VALUE)
                    continue;

                rooms[x][y] = rooms[pos[0]][pos[1]] + 1;
                queue.offer(new int[] {x, y});
            }
        }
    }
}