LeetCode 994. 腐烂的橘子
题目
在给定的网格中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
示例 1：
![]()
输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：
输入：[[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
示例 3：
输入：[[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
提示：
1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] 仅为 0、1 或 2
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotting-oranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
思路1-BFS，广度优先，使用优先队列
- 先统计一遍所有的好坏橘子数量，若有任意一种为0，可快速返回；
- 初始坏橘子入队列，然后每次取完队列里的所有坏橘子并尝试感染附近的橘子，感染到一个就减去一个好橘子数量并把感染到的橘子加入队列，但是这是下一轮的扩散橘子，跟本轮的要分开这里要注意，每轮只要有感染到就加一分钟，直到最后一轮无橘子可感染；
- 最后检查好橘子还有没有再返回对应结果；
思路2-DFS，深度优先，使用递归给坏橘子加一个腐败值的概念，求最大腐败值即可
- 第一次遍历遇到坏橘子就开始DFS，并用一个boolean记录；
- 初始坏橘子不断向四周扩散，且中途忽略腐败值小于其自身的值（DFS剪枝），如此递归；
- 最后一次遍历，若还有好橘子直接返回，若第一次的boolean为false，则返回0，否则返回最大腐败值-2；
总结：BFS是使用队列/优先队列去解决，而DFS是使用栈/递归去解决问题
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
| package leetcode;
import java.util.ArrayDeque;
import java.util.Deque;
public class LeetCode_0994 {
}
class Solution_0994 {
public int orangesRotting_1(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int goodG = 0;
Deque<int[]> deque = new ArrayDeque<int[]>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
goodG++;
} else if (grid[i][j] == 2) {
deque.offer(new int[] { i, j });
}
}
}
if (goodG == 0) {
return 0;
}
if (goodG > 0 && deque.isEmpty()) {
return -1;
}
int[] d1 = new int[] { 1, -1, 0, 0 };
int[] d2 = new int[] { 0, 0, 1, -1 };
int minute = 0, badG;
while (!deque.isEmpty()) {
badG = deque.size();
while (badG-- > 0) {
int[] bad = deque.poll();
for (int i = 0; i < 4; i++) {
int x = bad[0] + d1[i];
int y = bad[1] + d2[i];
if (x > -1 && x < m && y > -1 && y < n && grid[x][y] == 1) {
deque.offer(new int[] { x, y });
grid[x][y] = 2;
goodG--;
}
}
}
minute++;
}
return goodG == 0 ? minute - 1 : -1;
}
public int orangesRotting_2(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
boolean bad = false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
bad = true;
dfs(grid, i, j, 2);
}
}
}
int maxBad = 2;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int k = grid[i][j];
if (k == 1) {
return -1;
}
maxBad = Math.max(maxBad, k);
}
}
return !bad ? 0 : maxBad - 2;
}
private void dfs(int[][] grid, int x, int y, int val) {
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) {
return;
} else if (grid[x][y] != 1 && grid[x][y] < val) {
return;
} else {
grid[x][y] = val;
val++;
dfs(grid, x - 1, y, val);
dfs(grid, x + 1, y, val);
dfs(grid, x, y - 1, val);
dfs(grid, x, y + 1, val);
}
}
}
|
