题目链接
注意点
解法
解法一：bfs。首先先统计所有新鲜的橘子数目fresh，如果fresh大于0则一直执行bfs。我们只处理昨天刚腐烂的橘子，grid[i][j]的值就表示第几天腐烂的橘子，由于新鲜橘子的值一开始就是2，所以每次修改的时候都要改为day+3即 day+1+2（2是本来就有的，1表示经过了一天）。如果bfs之后发现新鲜橘子数没有减少则return -1，否则继续下一天的腐烂。
class Solution {
public:
int bfs(vector<vector<int>>& grid,int x,int y,int day)
{
if(x < 0||y < 0||x >= grid.size()||y >= grid[x].size()||grid[x][y] != 1) return 0;
grid[x][y] = day+3;
return 1;
}
int orangesRotting(vector<vector<int>>& grid) {
int i,j,day = 0,fresh = 0;
for(i = 0;i < grid.size();i++)
{
for(j = 0;j < grid[i].size();j++)
{
if(grid[i][j] == 1) fresh += 1;
}
}
while(fresh > 0)
{
int old_fresh = fresh;
for(i = 0;i < grid.size();i++)
{
for(j = 0;j < grid[i].size();j++)
{
if(grid[i][j] == day+2)
{
fresh -= bfs(grid,i,j+1,day)+bfs(grid,i,j-1,day)+bfs(grid,i+1,j,day)+bfs(grid,i-1,j,day);
}
}
}
if(old_fresh == fresh) return -1;
day++;
}
return day;
}
};
小结
- bfs重要的是找好边界条件以及每次修改的值。