力扣994：腐烂的橘子(BFS)

简单的广度优先搜索（BFS）问题：用队列存储每批腐烂的橘子。按批次取出腐烂的橘子，取出腐烂橘子的同时放入由新鲜变腐烂的橘子。

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    
    int[][] dist = {
    {
    -1,0},{
    1,0},{
    0,1},{
    0,-1}};//上下左右四个方向
    public int orangesRotting(int[][] grid) {
    
        int time = 0;//计时
        Queue<int[]> queue = new LinkedList<int[]>();
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] booleans = new boolean[n][m];
        for(int i = 0;i < n;i++){
    
            for(int j = 0;j < m;j++){
    
                if(grid[i][j] == 2){
    //首批腐烂的橘子赋值为true，防止重复遍历
                    queue.offer(new int[]{
    i,j});//腐烂的橘子加入队列
                    booleans[i][j] = true;
                }
                if(grid[i][j] == 0){
    //空单元格不做处理，防止遍历设值为true
                    booleans[i][j] = true;
                }
            }
        }
        int[] a = new int[2];
        while(!queue.isEmpty()){
    
            int num = queue.size();//每批腐烂橘子的个数
            int flag = 0;//若腐烂橘子能感染新鲜的橘子就改变flag的值。
            for(int number = 0;number < num;number++){
    
                a = queue.poll();
                for(int i = 0;i < 4;i++){
    
                    int x = a[0] + dist[i][0];
                    int y = a[1] + dist[i][1];
                    if(x>=0&&y>=0&&x<n&&y<m&&booleans[x][y]!=true){
    
                        grid[x][y] = 2;
                        queue.offer(new int[]{
    x,y});
                        booleans[x][y] = true;
                        flag = 1;
                    }
                }
            }
            if(flag == 1){
    
                time++;
            }
        }
        //遍历所有单元格，若存在新鲜橘子则返回-1，否则返回时间。
        for(int i = 0; i < n;i++){
    
            for(int j = 0;j < m;j++){
    
                if(grid[i][j] == 1){
    
                    return -1;
                }
            }
        }
        return time;
    }
}