leetcode 994. Rotting Oranges | 994. 腐烂的橘子（BFS）

本文主要是介绍leetcode 994. Rotting Oranges | 994. 腐烂的橘子（BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

https://leetcode.com/problems/rotting-oranges/
在这里插入图片描述

题解

和 leetcode 542. 01 Matrix | 542. 01 矩阵（图解，广度优先搜索）这道题几乎没有区别，直接用 542 的图，来讲一下“感染” 的过程，实际上就是个 BFS

在这里插入图片描述
只不过本题的 0,1,2 都被占用了，所以我们用 term=3 开始，标记感染轮数。感染过程中，每一轮 term+1，并且记录每一轮感染的数量 incr。如果某一轮出现 incr=0，即没有任何 orange 被感染，则说明感染过程结束，退出循环。

最后，感染完成后，检查一下矩阵中有没有剩余 1.

class Solution {public int orangesRotting(int[][] grid) {int M = grid.length;int N = grid[0].length;int incr = 1; // num of affected in this termint term = 3; // 0, 1, 2 already in use, so we mark 'affected' from term=3. term will incr by 1 in each round.while (incr > 0) {incr = 0;for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {if (grid[i][j] == term - 1) { // grid[i][j] == term - 1 means this coordinate is affected in the last termif (i - 1 >= 0 && grid[i - 1][j] == 1) { // affect leftgrid[i - 1][j] = term;incr++;}if (i + 1 < M && grid[i + 1][j] == 1) { // affect rightgrid[i + 1][j] = term;incr++;}if (j - 1 >= 0 && grid[i][j - 1] == 1) { // affect upgrid[i][j - 1] = term;incr++;}if (j + 1 < N && grid[i][j + 1] == 1) { // affect downgrid[i][j + 1] = term;incr++;}}}}term++;}// check no 1for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {if (grid[i][j] == 1) return -1;}}return term - 4;}
}