GuilinDev
Lc0994
05 August 2008
994 Rotting Oranges
题目
In a given grid, each cell can have one of three values:
- the value 0 representing an empty cell;
- the value 1 representing a fresh orange;
- the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.
Example 1:
1
2
Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:
1
2
3
Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:
1
2
3
Input: [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Note:
- 1 <= grid.length <= 10
- 1 <= grid[0].length <= 10
- grid[i][j] is only 0, 1, or 2.
分析
这道题计算烂番茄对周围的影响的层数（天数），因为是一层层往外扩散，所以要想到可以用BFS来做，BFS的写法比较固定，使用Queue，首先统计所有烂橘子的坐标放入到队列中，同时计算好橘子的个数；然后将每个烂橘子的坐标取出，将其周围四个方向的好橘子转变为烂橘子，同时将新产生的烂橘子坐标放入queue中，每次从queue中取出一个烂橘子的坐标就代表过了一分钟，如此一直到queue中为空。
代码
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
class Solution {
private final int[][] dirs = { {-1, 0},{0, -1},{0, 1},{1, 0} };
public int orangesRotting(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return -1;
}
int rows = grid.length;
int cols = grid[0].length;
Queue<int[]> queue = new ArrayDeque<>();
int fresh = 0;
// 统计所有烂番茄的坐标 - 接下来会用到这个坐标进行BFS，并计算新鲜番茄的个数
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 2) {
//将烂番茄的坐标存入到队列中
queue.offer(new int[]{i, j});
} else if (grid[i][j] == 1) { //这里统计多少个新鲜的，以免最后还要再扫描一遍看新鲜是否还有剩
fresh++;
}
}
}
if (fresh == 0) {
return 0;
}
int minutes = 0;
while (!queue.isEmpty()) {
minutes++; //往外扩散一层
int currSize = queue.size();
for (int i = 0; i < currSize; i++) {
int[] curr = queue.poll(); //BFS将当前烂番茄的坐标取出并计算四周
for (int[] dir : dirs) { // 遍历四个方向
int newX = curr[0] + dir[0];
int newY = curr[1] + dir[1];
// 只感染新鲜番茄
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] == 1) {
queue.offer(new int[]{newX, newY});
grid[newX][newY] = 2;
fresh--;
}
}
}
}
return fresh > 0 ? -1 : minutes - 1; //- 1是因为比如共两层但只扩散了一次
}
}