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 than2147483647.

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

Basic BFS problem. Add all cells of gates to the queue. Now for each cell polled out, check all its neighbors, update all neighbors that are valid cells and have distance to a gate larger than current one plus one.

public void wallsAndGates(int[][] rooms) {
        Queue queue = new LinkedList();
        int r = rooms.length, c = rooms[0].length;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (rooms[i][j] == 0) {
                    queue.add(i * c + j);
                }
            }
        }
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int[] d : dirs) {
                int x = curr / c + d[0];
                int y = curr % c + d[1];
                if (x < 0 || x >= r || y < 0 || y >= c ||
                    rooms[x][y] <= rooms[x - d[0]][y - d[1]] + 1) {
                    continue;
                }
                rooms[x][y] = rooms[x - d[0]][y - d[1]] + 1;
                queue.add(x * c + y);
            }
        }
    }