做线上网站需要多少钱,移动互联网在财务会计领域的应用,上海最新通报: 上海最新通报,番禺网站建设外包1. 题目
在给定的网格中#xff0c;每个单元格可以有以下三个值之一#xff1a;
值 0 代表空单元格#xff1b; 值 1 代表新鲜橘子#xff1b; 值 2 代表腐烂的橘子。 每分钟#xff0c;任何与腐烂的橘子#xff08;在 4 个正方向上#xff09;相邻的新鲜橘子都会腐烂…1. 题目
在给定的网格中每个单元格可以有以下三个值之一
值 0 代表空单元格 值 1 代表新鲜橘子 值 2 代表腐烂的橘子。 每分钟任何与腐烂的橘子在 4 个正方向上相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回 -1。 示例 1
输入[[2,1,1],[1,1,0],[0,1,1]]
输出4示例 2
输入[[2,1,1],[0,1,1],[1,0,1]]
输出-1
解释左下角的橘子第 2 行 第 0 列永远不会腐烂因为腐烂只会发生在 4 个正向上。示例 3
输入[[0,2]]
输出0
解释因为 0 分钟时已经没有新鲜橘子了所以答案就是 0 。提示
1 grid.length 10
1 grid[0].length 10
grid[i][j] 仅为 0、1 或 2来源力扣LeetCode 链接https://leetcode-cn.com/problems/rotting-oranges 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 图的广度优先搜索
先将所有腐烂的位置加入队列同时记录好的橘子个数访问过的位置改为-1visited标记对队列里的腐烂位置开始BFS不等于-1没访问且等于1没烂的加入队列同时好橘子减1
class Solution {
public:int orangesRotting(vectorvectorint grid) {int i, j, k, len, x, y, goodfruits 0;int m grid.size(), n grid[0].size(), minutes -1;queuepairint,int q;for(i 0; i m; i)for(j 0; j n; j)if(grid[i][j] 2){q.push({i,j});//烂橘子入队grid[i][j] -1;//访问过了}else if(grid[i][j] 1)goodfruits;//好橘子个数if(goodfruits 0)return 0;//没有好橘子直接返回vectorpairint,int dir {{1,0},{-1,0},{0,1},{0,-1}};while(!q.empty()){len q.size();while(len--){for(k 0; k 4; k){x q.front().firstdir[k].first;y q.front().seconddir[k].second;if(x0 xm y0 yn grid[x][y]! -1 grid[x][y]1){ //没访问过 是好橘子q.push({x,y});grid[x][y] -1;//访问了goodfruits--;//烂了}}q.pop();}minutes;}if(goodfruits)return -1;//还有好橘子所以不可能全烂掉return minutes;}
};
