一、题目
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值
0代表空单元格；- 值
1代表新鲜橘子；- 值
2代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
二、示例
2.1> 示例 1：
【输入】grid = [[2,1,1],[1,1,0],[0,1,1]]
【输出】4
2.2> 示例 2：
【输入】grid = [[2,1,1],[0,1,1],[1,0,1]]
【输出】-1
【解释】左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
2.3> 示例 3：
【输入】grid = [[0,2]]
【输出】0
【解释】因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
提示：
- m == grid.length
- n == grid[i].length
-
1<= m, n <=10 - grid[i][j] 仅为
0、1或2
三、解题思路
根据题目描述，我们要计算出单元格中没有新鲜橘子为止所必须经过的最小分钟数。由于腐烂的橘子可以将好的橘子也变腐烂，所以，我们需要采用某种方式，将这种橘子腐烂的轮次模拟计算出来。
这里，我们首先创建一个队列，即：Deque。然后先将矩阵中腐烂的橘子保存到deque中。然后获取deque中存储的腐烂橘子的个数num，那么当num个橘子从deque中出栈之后，就表示该轮次执行完毕。
那么，当我们从队列deque中弹出腐烂的橘子之后，我们会将该烂橘子的上、下、左、右的新鲜橘子都变为烂橘子，即：grid[x][y] = 2。然后将刚刚变烂的句子放入到deque中，准备作为后续下一轮需要操作的烂橘子。
那么，需要补充一点的就是，当我们计算矩阵中腐烂橘子的同时，也可以同时获得新鲜的橘子的个数fresh，当面当我们发现fresh等于0的时候，则说明所有的好橘子都被腐烂了，返回操作的轮次数；而当我们操作完所有的腐烂橘子，而fresh依然不为0，则说明某些新鲜的橘子是不会被传染腐烂的，则直接返回-1即可。
以上就是本题的解题思路。为了方便大家理解，请参照下图图解即可：
四、代码实现
class Solution {
int fresh = 0, minute = 0;
Deque<int[]> deque = new ArrayDeque();
public int orangesRotting(int[][] grid) {
int result = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 2) deque.addLast(new int[]{i, j});
if (grid[i][j] == 1) fresh++;
}
}
while (fresh > 0 && !deque.isEmpty()) {
minute++;
int nums = deque.size();
for (int i = 0; i < nums; i++) {
int[] cell = deque.removeFirst();
int x = cell[0], y = cell[1];
rot(grid, x - 1, y); // 查看上方单元格
rot(grid, x + 1, y); // 查看下方单元格
rot(grid, x, y - 1); // 查看左侧单元格
rot(grid, x, y + 1); // 查看右侧单元格
}
}
return fresh > 0 ? -1 : minute;
}
public void rot(int[][] grid, int x, int y) {
if (x >= 0 && y >=0 && x < grid.length && y < grid[0].length && grid[x][y] == 1) {
grid[x][y] = 2;
deque.addLast(new int[]{x, y});
fresh--;
}
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
