286. Walls and Gates

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.

For example, given the 2D grid:

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:

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

Solution:

We use BFS and start with multi locations with value 0.

When we find an empty room is the neighbor of the current room, we add its value by 1.

Finally we reach all reachable rooms.

Checkout Diet Coke's explanation



Code:

public class Solution {
    
    private final int[] d = {0, 1, 0, -1, 0};
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0) {
            return;
        }
        if (rooms[0] == null || rooms[0].length == 0) {
            return;
        }
        Queue<Integer> queue = new LinkedList<>();
        int m = rooms.length;
        int n = rooms[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    queue.offer(i * n + j);
                }
            }
        }
        while (!queue.isEmpty()) {
            int x = queue.poll();
            int i = x / n;
            int j = x % n;
            for (int k = 0; k < 4; k++) {
                int p = i + d[k];
                int q = j + d[k + 1];
                while (p >= 0 && p < m && q >= 0 && q < n && rooms[p][q] == Integer.MAX_VALUE) {
                    rooms[p][q] = rooms[i][j] + 1;
                    queue.offer(p * n + q);
                }
            }
        }
    }
}