994. 腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

示例 3：

输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

994. 腐烂的橘子 - 力扣（LeetCode）

class Solution {
    /**
    2024年7月29日22:19:02
    这个得用BFS来模拟时间的流逝，不能用dfs了
     */
    public int orangesRotting(int[][] grid) {
        if(grid==null || grid.length==0){
            return -1;
        }
        int rows=grid.length;
        int cols=grid[0].length;
        Queue<int[] > que=new LinkedList<>();
        int freshOrange=0;

        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(grid[i][j]==2){
                    que.offer(new int[] {i,j});
                } else if(grid[i][j]==1){
                    freshOrange++;
                }
            }
        }
        if(freshOrange==0){
            return 0;
        }

        int minutes=0;
        boolean haveBadOrange=false;

        int[] dx={1,-1,0,0};
        int[] dy={0,0,1,-1};

        while(!que.isEmpty()){
            int size=que.size();
            haveBadOrange=false;
            for(int i=0;i<size;i++){
                int[] tmp=que.poll();
                int row=tmp[0];
                int col=tmp[1];
                for(int k=0;k<4;k++){
                    // 先更新x,y值再做if判断，更简单
                    int x=row+dx[k];
                    int y=col+dy[k];
                    if(x>=0 && x<grid.length && y>=0 && y<grid[0].length &&grid[x][y]==1){
                        grid[x][y]=2;
                        que.offer(new int[]{x,y});
                        // 说明有变腐烂的橘子
                        haveBadOrange=true;
                        // 更新下新鲜橘子数量，有可能存在新鲜橘子周围没有腐烂橘子的情况
                        freshOrange--;
                    }
                }
            }
            if(haveBadOrange){
                minutes++;
            }
        }

        return freshOrange==0?minutes:-1;

    }
}