LeetCode hot100——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 。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j]仅为0、1或2

题解

class Solution { public int orangesRotting(int[][] grid) { Queue<int[]> queue = new LinkedList<>();//存每轮腐烂橘子 int fresh = 0; for(int i = 0;i < grid.length;i++){ for(int j = 0;j < grid[0].length;j++){ if(grid[i][j] == 1) fresh++;//新鲜橘子 else if(grid[i][j] == 2) queue.offer(new int[]{i,j});//腐烂橘子入队 } } if(fresh == 0) return 0;//所有单元格都没新鲜橘子 int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};//上下左右 int minute = -1;//初始腐烂橘子++记0 while(!queue.isEmpty()){ int size = queue.size(); for(int i = 0;i < size;i++){ int[] cur = queue.poll(); int r = cur[0]; int c = cur[1]; //对腐烂橘子四周扩散 for(int[] dir:dirs){ int nr = dir[0] + r; int nc = dir[1] + c; if(nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] == 1){ grid[nr][nc] = 2; fresh--; queue.offer(new int[]{nr,nc}); } } } minute++; } return fresh > 0 ? -1 : minute; } }