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 2^31- 1 = 2147483647to represent INFas you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to itsnearestgate. If it is impossible to reach a gate, it should be filled withINF.

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

Thoughts:

1. BFS and fill the empty rooms with current distance

Code: T: O(mn); S:O(mn)

class Solution {
    public void wallsAndGates(int[][] rooms) {
        if(rooms.length == 0|| rooms[0].length == 0) return;
        Queue<int[]> queue = new LinkedList();
        int [] d = {0,1,0,-1,0};
        for(int i = 0; i < rooms.length; i++){
            for(int j =0; j< rooms[0].length; j++){
                if(rooms[i][j] == 0) queue.offer(new int[]{i,j});
            }
        }

        while(!queue.isEmpty()){
            int [] pos  = queue.poll();
            int row = pos[0], col = pos[1];
            for(int i = 0; i < 4; i++){
                int x = row + d[i];
                int y = col + d[i+1];
                if(x >= 0 && x < rooms.length && y>=0 && y< rooms[0].length && rooms[x][y] == Integer.MAX_VALUE){
                    rooms[x][y] = rooms[row][col] + 1;
                    queue.offer(new int[]{x,y});
                }
            }

        }

    }
}