286. Walls and Gates

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.

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

---

------------------------------
典型的BFS，注意的是需要从所有0的位置同时开始走
O(m * n), m n 为2维数组的长宽。因为一个INF的点最多只被走一次

class Solution {

    public void wallsAndGates(int[][] rooms) {
        Queue<Pair> que = getQueue(rooms);
        
        fillRooms(rooms, que);
    }
    
    private void fillRooms(int[][] rooms, Queue<Pair> que) {
        
        int[][] coord = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        
        while (!que.isEmpty()) {
            
            Pair top = que.poll();
            for (int[] arr : coord) {
                int r = top.row + arr[0];
                int c = top.col + arr[1];
                
                if (r >= 0 && r < rooms.length && c >= 0 && c < rooms[0].length
                   && rooms[r][c] == 2147483647) {
                    rooms[r][c] = rooms[top.row][top.col] + 1;
                    que.add(new Pair(r, c));
                }
            }
        }
    }
    
    private Queue<Pair> getQueue(int[][] rooms) {
        Queue<Pair> que = new LinkedList<>();
        
        for (int i = 0; i < rooms.length; i++) {
            for (int j = 0; j < rooms[0].length; j++) {
                if (rooms[i][j] == 0) {
                    que.add(new Pair(i, j));
                }
            }
        }
        
        return que;
    }
}

class Pair{
    public int row;
    public int col;
    public Pair(int row, int col) {
        this.row = row;
        this.col = col;
    }
}