友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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
思路分析
对网格进行遍历，让橘子逐渐加深腐烂程度 2 → 3 → 4 → …，同时传染给相邻橘子，记录有被传染的橘子，如果被传染橘子数量不为0，则进行下一轮遍历。最后，再判断一下网格中是否还有新鲜橘子，如有，则返回 -1，没有则计算耗时。
看题解，记录腐烂橘子和新鲜橘子的位置，然后进行遍历的做法也不错。如下图：
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-15 22:20:47
*/
public int orangesRotting(int[][] grid) {
int rotted = 2;
while (rot(grid, rotted) > 0) {
rotted++;
}
int m = grid.length;
int n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
return -1;
}
}
}
return rotted - 2;
}
private int rot(int[][] grid, int roted) {
int m = grid.length;
int n = grid[0].length;
int count = 0;
int next = roted + 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != roted) {
continue;
}
grid[i][j] = next;
// 上
if (i > 0 && grid[i - 1][j] == 1) {
grid[i - 1][j] = next;
count++;
}
// 下
if (i < m - 1 && grid[i + 1][j] == 1) {
grid[i + 1][j] = next;
count++;
}
// 左
if (j > 0 && grid[i][j - 1] == 1) {
grid[i][j - 1] = next;
count++;
}
// 右
if (j < n - 1 && grid[i][j + 1] == 1) {
grid[i][j + 1] = next;
count++;
}
}
}
return count;
}