Leetcode题解
Search…
994.Rotting Oranges
994.Rotting Oranges
难度:Easy
在给定的网格中，每个单元格可以有以下三个值之一：
值 0 代表空单元格； 值 1 代表新鲜橘子； 值 2 代表腐烂的橘子。 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
示例 1：
oranges.png
1
输入：[[2,1,1],[1,1,0],[0,1,1]]
2
输出：4
3
示例 2：
4
5
输入：[[2,1,1],[0,1,1],[1,0,1]]
6
输出：-1
7
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
8
示例 3：
9
10
输入：[[0,2]]
11
输出：0
12
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
13
14
15
提示：
16
17
1 <= grid.length <= 10
18
1 <= grid[0].length <= 10
19
grid[i][j] 仅为 0、1 或 2
Copied!
解决方法，可以一步遍历一次，将相邻有2的值为1的单元格变成2。这里在遍历过程中先变为-1，以免将刚变成2的当做腐烂橘子继续传递。
为了方便遍历，将数组扩展一周，这样每次都可以比较上下左右四个方向。
当不可遍历时，就是无法继续传递的时候，需要判断当前是否还存在1，如果存在，则表示无法完全腐烂，这里使用布尔常量can来表示。
flag表示是否已经无法继续遍历。
层次遍历可以使用递归实现。
1
class Solution {
2
bool can=true;
3
int getCount(vector<vector<int>>& grid)
4
{
5
bool flag=true;
6
bool other=false;
7
for(int i=1;i< grid.size()-1;i++)
8
{
9
for(int j=1;j<grid[0].size()-1;j++)
10
{
11
if(grid[i][j] ==1 && (grid[i][j+1]==2 || grid[i+1][j] ==2 || grid[i-1][j] ==2 || grid[i][j-1] ==2 ))
12
{
13
grid[i][j]=-1;
14
flag=false;
15
}
16
}
17
}
18
19
for(int i=0;i< grid.size();i++)
20
{
21
for(int j=0;j<grid[0].size();j++)
22
{
23
if(grid[i][j] ==-1) grid[i][j]=2;
24
if(grid[i][j]==1) other=true;
25
}
26
27
}
28
if(flag )
29
{
30
if(other) can=false;
31
return 0;
32
}
33
return 1+getCount(grid);
34
35
}
36
public:
37
int orangesRotting(vector<vector<int>>& grid) {
38
vector<vector<int>>Lgrid(grid.size()+2,vector<int>(grid[0].size()+2,0));
39
for(int i=1;i<Lgrid.size()-1;i++)
40
for(int j=1;j<Lgrid[0].size()-1;j++)
41
Lgrid[i][j]=grid[i-1][j-1];
42
int res= getCount(Lgrid);
43
return can?res:-1;
44
45
46
}
47
};
Copied!
执行用时 :4 ms, 在所有 C++ 提交中击败了98.79%的用户 内存消耗 :9.2 MB, 在所有 C++ 提交中击败了89.23%的用户
Last modified 5mo ago
Copy link