LeetCode220726_52、腐烂的橘子

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

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

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

示例 1：

图1 腐烂的橘子示例图 

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/rotting-oranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解，BFS寻找感染最短距离，记录新鲜橘子数量，用以返回判断，遍历时，一轮一轮感染，每次将一层队列内的烂橘子全部整完在进行下一轮。

class Solution{
    public int orangesRotting(int[][] grid){
        int count = 0;
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 1){
                    count++;
                } else if(grid[i][j] == 2){
                    queue.offer(new int[]{i,j});
                }
            }
        }
        int round = 0;
        while(count > 0 && !queue.isEmpty()){
            round++;
            int size = queue.size();
            for(int m = 0; m < size; m++){
                int[] pos = queue.poll();
                int x = pos[0];
                int y = pos[1];
                int[] dx = {1, 0, 0, -1};
                int[] dy = {0, -1, 1, 0};
                for(int n = 0; n < 4; n++){
                    int nextx = x + dx[n];
                    int nexty = y + dy[n];
                    if(nextx >= 0 && nextx < grid.length && nexty >= 0 && nexty < grid[0].length && grid[nextx][nexty] == 1){
                        grid[nextx][nexty] = 2;
                        count--;
                        queue.offer(new int[]{nextx,nexty});
                    }
                }
            }
        }
        if(count == 0){
            return round;    
        }else{
            return -1;
        }
    }
}