Rotting Oranges

目录

• 题目链接
• 注意点
• 解法
• 小结

题目链接

Rotting Oranges - LeetCode

注意点

解法

解法一：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重要的是找好边界条件以及每次修改的值。