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

Solution1：BFS

Time Complexity: O(mn) Space Complexity: O(mn)

Solution1.b：BFS level(dist)

Time Complexity: O(mn) Space Complexity: O(mn)

Solution2：DFS染色

Time Complexity: O(mn) Space Complexity: O(mn)

Solution1 Code：

class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms.length == 0 || rooms[0].length == 0) return;
        
        Queue<int[]> queue = new LinkedList<>();
        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[] top = queue.poll();
            int row = top[0], col = top[1];
            if (row > 0 && rooms[row - 1][col] == Integer.MAX_VALUE) {
                rooms[row - 1][col] = rooms[row][col] + 1;
                queue.offer(new int[]{row - 1, col});
            }
            if (row < rooms.length - 1 && rooms[row + 1][col] == Integer.MAX_VALUE) {
                rooms[row + 1][col] = rooms[row][col] + 1;
                queue.offer(new int[]{row + 1, col});
            }
            if (col > 0 && rooms[row][col - 1] == Integer.MAX_VALUE) {
                rooms[row][col - 1] = rooms[row][col] + 1;
                queue.offer(new int[]{row, col - 1});
            }
            if (col < rooms[0].length - 1 && rooms[row][col + 1] == Integer.MAX_VALUE) {
                rooms[row][col + 1] = rooms[row][col] + 1;
                queue.offer(new int[]{row, col + 1});
            }
        }
    }
}

Solution1.b Code：

class Solution {
    public void wallsAndGates(int[][] rooms) {
        if(rooms == null || rooms.length == 0 || rooms[0].length == 0) return;
        
        Queue<int[]> queue = new LinkedList<>();
        for(int row = 0; row < rooms.length; row++) {
            for(int col = 0; col < rooms[0].length; col++) {
                if(rooms[row][col] == 0) {
                    queue.offer(new int[]{row, col});
                }
            }
        }
        
        int dist = 0;
        while(!queue.isEmpty()) {
            dist++;
            int queue_size = queue.size();
            for(int l = 0; l < queue_size; l++) {
                int[] coord = queue.poll();
                
                int[] step_row = new int[] {0, 0, -1, 1};
                int[] step_col = new int[] {-1, 1, 0, 0};
                
                for(int i = 0; i < 4; i++) {
                    int[] new_coord = new int[]{coord[0] + step_row[i], coord[1] + step_col[i]};
                    if(new_coord[0] < 0 || new_coord[0] > rooms.length - 1 || new_coord[1] < 0 
                       || new_coord[1] > rooms[0].length - 1) {
                        continue;
                    }
                    
                    if(rooms[new_coord[0]][new_coord[1]] == Integer.MAX_VALUE) {
                        rooms[new_coord[0]][new_coord[1]] = dist;
                        queue.offer(new_coord);
                    }
                }
            }
        }
    }
}

Solution2 Code：

class Solution {
    public void wallsAndGates(int[][] rooms) {
        if(rooms.length==0||rooms[0].length==0)
            return;
        int n = rooms.length, m = rooms[0].length;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(rooms[i][j]==0)
                    DFS(rooms, i, j, 0);
            }
        }
    }
    
    public void DFS(int[][] rooms, int i, int j, int step){
        if(i<0||j<0||i>=rooms.length||j>=rooms[0].length||rooms[i][j]==-1||rooms[i][j]<step)
            return;
        rooms[i][j] = step;
        DFS(rooms, i+1, j, step+1);
        DFS(rooms, i-1, j, step+1);
        DFS(rooms, i, j+1, step+1);
        DFS(rooms, i, j-1, step+1);
    }
}