腐烂的橘子

标签：int res 腐烂 ++ grid 橘子

在给定的 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/rotting-oranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路1

广度优先搜索模拟橘子腐烂的过程，一层层地去腐烂周围的橘子。首先第一层就是一开始就腐烂的橘子，将其全部加入队列中。第二层是就是将第一层的橘子全部弹出并腐烂周围的橘子并加入到队列中，并不断下去直到没有腐烂或者全部腐烂为止。其实也可以套多源BFS的模板，从多个腐烂的源头出发，记录到最近的未腐烂的橘子的最短距离也就是时间，如果使用矩阵存储的话空间复杂度就是O(m*n)了。

code

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {

        int height =grid.size(),width = grid[0].size();

        int dx[4] = {-1,1,0,0};
        int dy[4] = {0,0,-1,1};

        int res = 0;
        int cnt = 0;
        
        queue<pair<int,int>> q;

        for(int i = 0;i < height;i ++)
        {
            for(int j = 0;j < width;j ++)
            {
                if(grid[i][j] == 1) res ++;
                if(grid[i][j] == 2) q.push({i,j});
            }
        }

        if(res == 0) return 0;

        while(!q.empty())
        {
            int len = q.size();
            cnt ++;
            for(int i = 0;i < len;i ++)
            {
                pair<int,int> cur = q.front();
                q.pop();

                for(int  j = 0;j < 4;j ++)
                {
                    int x = cur.first + dx[j];
                    int y = cur.second + dy[j];

                    if(x >= 0 && x < height && y >= 0 && y < width && grid[x][y] == 1)
                    {
                        grid[x][y] = 2;
                        res --;
                        if(res == 0) return cnt;
                        q.push({x,y});
                    }
                }
                
            }
        }

        if(res > 0) return -1;
        else return cnt;
    }
};

标签：int,res,腐烂,++,grid,橘子
From： https://www.cnblogs.com/huangxk23/p/17136810.html

腐烂的橘子