package Code;

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

public class Code994 {
    public static int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> q = new LinkedList<>();
        int fresh = 0;
        //初始化
        for(int i = 0; i< m; i++){
            for(int j= 0; j< n; j++){
                if(grid[i][j] == 2){
                    q.offer(new int[]{i,j});
                }else if(grid[i][j] == 1){
                    fresh++;
                }
            }
        }
        //搜索
        int[][] dir = {{-1,0},{0,-1},{1,0},{0,1}};
        int times = 0;
        while(!q.isEmpty() && fresh>0){
            int size = q.size();
            for(int i =0; i<size; i++){
                int[] cur = q.poll();
                int x = cur[0];
                int y = cur[1];
                for(int[] d : dir){
                    int newX = x+ d[0];
                    int newY = y+ d[1];
                    if(newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1){
                        grid[newX][newY] = 2;
                        q.offer(new int[]{newX, newY});
                        fresh--;
                    }
                }
            }
            times++;
        }
        return fresh == 0? times: -1;
    }
    public static void main(String[] args) {
        int[][] grid = {
                {2, 1, 1},
                {1, 1, 0},
                {0, 1, 1}
        };

        int minutes = orangesRotting(grid);
        System.out.println("直到没有新鲜橘子为止所必须经过的最小分钟数: " + minutes);

    }
}