Walls and Gates 07/30

You are given a m x n 2D grid initialized with these three possible values.

-1 - A wall or an obstacle. 0 - A gate. 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 gate, it should be filled with INF.Have you met this question in a real interview? Yes

Example

Given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

return the result:

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

先找到每一个0在矩阵中的位置，把他的坐标分别放进x queue，和y queue里，然后遍历这些0 上下左右每一个点的值，如果是inf的话，就把他们放进x queue和y queue里，然后只更新1，BFS 做法，逐层遍历 逐层更新

public class Solution {
    /**
     * @param rooms: m x n 2D grid
     * @return: nothing
     */
    public void wallsAndGates(int[][] rooms) {
        // write your code here
        
        int n = rooms.length;
        if(n == 0){
            return;
        }
        
        int m = rooms[0].length;
        
        //用来找到一个点的上下左右点
        
        int[] dx= {1,0,-1,0};
        int[] dy = {0,1,0,-1};
        Queue<Integer> qx = new LinkedList<>();
        Queue<Integer> qy = new LinkedList<>();
        
        for (int i =0;i < n ;i++ ){
            for(int j = 0; j < m; j++){
                if(rooms[i][j] == 0){
                    qx.offer(i);
                    qy.offer(j);
                }
            }
        } 
        
        while(!qx.isEmpty()){
            
            int cx = qx.poll();
            int cy = qy.poll();
            
            for(int i = 0; i < 4; ++i){
                int nx = cx+dx[i];
                int ny = cy + dy[i];
                
                if(nx < n && nx >= 0 && ny < m && ny >= 0 && rooms[nx][ny] == Integer.MAX_VALUE){
                    
                    
                    qx.offer(nx);
                    qy.offer(ny);
                    rooms[nx][ny] = rooms[cx][cy]+1;
                }
            }
        }
    }
}