# 994.Rotting Oranges

**994.Rotting Oranges**

难度:Easy

> 在给定的网格中，每个单元格可以有以下三个值之一：

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

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

示例 1：

![oranges.png](https://i.loli.net/2019/07/19/5d31944093d2e98480.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%的用户


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/994.rotting_oranges.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.