题目链接

注意点

解法

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

巴特西

Rotting Oranges - LeetCode

题目链接

注意点

解法

小结

最新文章

热门文章