当前位置: 首页 > >

leetcode994.腐烂的橘子

发布时间:

题目描述

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


值 0 代表空单元格;
值 1 代表新鲜橘子;
值 2 代表腐烂的橘子。

每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。


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


提示:


    1 <= grid.length <= 101 <= grid[0].length <= 10grid[i][j] 仅为 012

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/rotting-oranges


解法

class Solution {
public:
int orangesRotting(vector>& grid)
{
if(grid.empty())
return -1;
int m=grid.size();//行数
int n=grid[0].size();//列数
queue> q;
int count=0;
for(int i=0;i {
for(int j=0;j {
if(grid[i][j]>0)
count++;//统计橘子的个数
if(grid[i][j]==2)
q.push(make_pair(i,j));//统计腐烂橘子的坐标
}
}
if(q.size()==count)
return 0;//所有的橘子都腐烂了
int res=0;//统计完全腐烂需要经过的最小分钟数
vector> direct={{-1,0},{0,-1},{1,0},{0,1}};//四个方向
while(!q.empty())
{
int size=q.size();//记录每一轮的腐烂的橘子的个数
while(size)
{
auto a=q.front();//自动类型判断
q.pop();
count--;//橘子数目减少一个,意味着不再考虑这个烂橘子
for(auto d:direct)
{
int x=a.first+d.first;
int y=a.second+d.second;//四个方向依次判断
if(x<0||y<0||x>=m||y>=n)//如果坐标超出范围,不做处理
continue;
if(grid[x][y]!=1)//空的位置或者已经是烂橘子
continue;
grid[x][y]=2;//如果这个位置是好的橘子,就会腐烂
q.push(make_pair(x,y));//将新变烂的橘子坐标入队
}
size--;//该层烂橘子数减1
}
res++;//轮数加1
}
return count==0?res-1:-1;
}
};



友情链接: