在给定的 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 。
为什么用BFS
由题目可知每过一分钟腐烂的橘子周围的新鲜橘子也会腐烂掉，我们需要返回给定网格中的橘子多久会全部腐烂，如果不能全部腐烂则返回1，这种网格问题一开始肯定会想到DFS，即深度优先遍历，但是仔细想想，每个腐烂橘子每分钟都会腐烂周围的橘子，我们对一个腐烂橘子深度搜索没有任何意义，所以思路转变为BFS，即广度优先搜索，有了这一层想法后思路也很简单了，通常BFS应用在树结构上，用来求最短路径。
何为广度优先搜索
官解：所谓广度优先搜索，就是从起点出发，每次都尝试访问同一层的节点，如果同一层都访问完了，再访问下一层，最后广度优先搜索找到的路径就是从起点开始的最短合法路径。
通俗地讲：BFS 可以看成是层序遍历。从某个结点出发，BFS 首先遍历到距离为 1 的结点，然后是距离为 2、3、4…… 的结点。因此，BFS 可以用来求最短路径问题。BFS 先搜索到的结点，一定是距离最近的结点。
BFS思路
对于本题目，每分钟腐烂的橘子都会感染周围的新鲜橘子，被感染的橘子再过一分钟又会感染周围新鲜橘子，直到感染所以可以感染到的新鲜橘子，这过程就很像BFS嘛，实际上这道题在我眼里也是一个求最短路径的模型，腐烂橘子到所有新鲜橘子的最短路径，路径的长度就是最后的时间。
对于树我们可以从根节点开始逐层遍历，如果本题初始状态只有一个腐烂橘子的话也一样，但是可能有多个腐烂橘子，所以我们要用多源BFS，也很简单，先遍历一遍数组记录每个初始状态的腐烂橘子。
一般BFS都是通过队列实现的，把最开始的腐烂橘子的下标储存在一个队列中，然后逐个出队找腐烂橘子周围的新鲜橘子，感染它并且将它入队，用来感染下一层橘子，因为题目要求路径，所以我们需要通过一个变量来保存每一层入队的被感染橘子的数量，在遍历完一层后结果要加一，当腐烂橘子周围再也没有新鲜橘子时退出循环，然后再次遍历网格，如果还有新鲜橘子则返回-1，没有的话返回结果。
细节处理
这里有一个细节int res = -1;和return res == -1 ? 0 : res;，为什么结果初始化为-1呢，因为最开始所有腐烂橘子入队时res也要加一，如果没有新鲜橘子的话返回0，但是初始化化为0的话就会返回1，这不合理。对于初始化可以这么理解，最开始有一个超级细菌，在0时刻感染了最开始腐烂的橘子，我们要求的是这些橘子感染其他橘子的时间，所以初始化结果为-1了。但是还有一种情况是网格里一个腐烂橘子都没有，这样的话根本就不会进入循环，最后返回-1也不合理，所以当最后结果为-1时返回0即可，如何解释呢，如果超级细菌最开始没有感染橘子，那么0时刻（开始感染的时刻）和-1时刻（所有橘子都是新鲜的）将没有任何区别，但是时间依然流动了。
完整代码如下：
Ps：还可以优化，在这基础上加一个变量保存新鲜橘子的数量，就不需要最后再遍历一次数组了，只需要判断该变量是否为0即可。
class Solution { public int orangesRotting(int[][] grid) { int m = grid.length; int n = grid[0].length; Deque<int[]> queue = new LinkedList<>(); //队列实现BFS for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 2) { queue.offer(new int[]{i, j}); //将最开始的腐烂橘子入队 } } } int res = -1; while (!queue.isEmpty()) { //还有可以被感染的橘子时循环 int q = queue.size(); //该变量保存每一层橘子的个数 res++; //走完一层就+1 for (int i = 0; i < q; i++) { //循环遍历一层 int[] temp = queue.poll(); int r = temp[0]; int c = temp[1]; if (r - 1 >= 0 && grid[r - 1][c] == 1) { //访问上边，如果不越界且为新鲜橘子则入队并且感染 queue.offer(new int[]{r - 1, c}); grid[r - 1][c] = 2; } if (r + 1 < m && grid[r + 1][c] == 1) { //下 queue.offer(new int[]{r + 1, c}); grid[r + 1][c] = 2; } if (c - 1 >= 0 && grid[r][c - 1] == 1) { //左 queue.offer(new int[]{r, c - 1}); grid[r][c - 1] = 2; } if (c + 1 < n && grid[r][c + 1] == 1) { //右 queue.offer(new int[]{r, c + 1}); grid[r][c + 1] = 2; } } } for (int i = 0; i < m; i++) { //遍历最后的结果 for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { //如果还有新鲜橘子返回-1 return -1; } } } return res == -1 ? 0 : res; //如果一开始没有腐烂橘子返回0，否则返回结果 } }
原文：https://leetcode.cn/problems/rotting-oranges/solution/by-nice-hermann9a2-tdws/
Original: https://www.cnblogs.com/liangren-na/p/16437624.html
Author: 良人呐
Title: 994.腐烂的橘子
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/619861/
转载文章受原作者版权保护。转载请注明原作者出处！