LeetCode 994、腐烂的橘子

994、腐烂的橘子

1）题目描述

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

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

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

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

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。

示例 3：

输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] 仅为 0、1 或 2

2）分析

广度优先搜索。

• 遍历grid存储所有烂橘子的位置，入队，并统计新鲜橘子的数量；
• 然后遍历队列，如果四周存在新鲜橘子 ，那么设置时间，然后添加进队列，新鲜橘子数量减一；
• 广度优先搜索结束后，如果新鲜橘子数量不为零，返回-1。

3）C++代码

class Solution {
    
public:
    int orangesRotting(vector<vector<int>>& grid) {
    
        int m=grid.size();
        int n=grid[0].size();
        int dx[4]={
    1,0,-1,0};
        int dy[4]={
    0,1,0,-1};
        int cnt_1=0;
        int res=0;
        queue<pair<int,int>> que;
        vector<vector<int>> timeCosted(m,vector<int> (n,0));


        //遍历网格，记录所有腐烂的橘子的坐标与新鲜橘子的数量
        for(int i=0;i<m;i++){
    
            for(int j=0;j<n;j++){
    
                if(grid[i][j]==2)
                    que.emplace(i,j);
                else if(grid[i][j]==1)
                    cnt_1++;
            }
        }

        //广度优先搜索
        while(!que.empty()){
    
            int x=que.front().first;
            int y=que.front().second;
            que.pop();
            for(int i=0;i<4;i++){
    
                int newX=x+dx[i];
                int newY=y+dy[i];
                if(newX>=0&&newX<m&&newY>=0&&newY<n&&grid[newX][newY]==1&&!timeCosted[newX][newY]){
    
                    timeCosted[newX][newY]=timeCosted[x][y]+1;
                    que.emplace(newX,newY);
                    if(grid[newX][newY]==1){
    
                        res=res>timeCosted[newX][newY]?res:timeCosted[newX][newY];
                        cnt_1-=1;
                        if(!cnt_1)
                            break;
                    }
                }
            }
        }
        return cnt_1?-1:res;
    }
};