994.Rotting Oranges

994.Rotting Oranges

难度:Easy

在给定的网格中,每个单元格可以有以下三个值之一:

值 0 代表空单元格; 值 1 代表新鲜橘子; 值 2 代表腐烂的橘子。 每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1。

示例 1:

oranges.png
输入:[[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

解决方法,可以一步遍历一次,将相邻有2的值为1的单元格变成2。这里在遍历过程中先变为-1,以免将刚变成2的当做腐烂橘子继续传递。 为了方便遍历,将数组扩展一周,这样每次都可以比较上下左右四个方向。 当不可遍历时,就是无法继续传递的时候,需要判断当前是否还存在1,如果存在,则表示无法完全腐烂,这里使用布尔常量can来表示。 flag表示是否已经无法继续遍历。 层次遍历可以使用递归实现。

class Solution {
bool can=true;
int getCount(vector<vector<int>>& grid)
{
bool flag=true;
bool other=false;
for(int i=1;i< grid.size()-1;i++)
{
for(int j=1;j<grid[0].size()-1;j++)
{
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 ))
{
grid[i][j]=-1;
flag=false;
}
}
}
for(int i=0;i< grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j] ==-1) grid[i][j]=2;
if(grid[i][j]==1) other=true;
}
}
if(flag )
{
if(other) can=false;
return 0;
}
return 1+getCount(grid);
}
public:
int orangesRotting(vector<vector<int>>& grid) {
vector<vector<int>>Lgrid(grid.size()+2,vector<int>(grid[0].size()+2,0));
for(int i=1;i<Lgrid.size()-1;i++)
for(int j=1;j<Lgrid[0].size()-1;j++)
Lgrid[i][j]=grid[i-1][j-1];
int res= getCount(Lgrid);
return can?res:-1;
}
};

执行用时 :4 ms, 在所有 C++ 提交中击败了98.79%的用户 内存消耗 :9.2 MB, 在所有 C++ 提交中击败了89.23%的用户