50.腐烂的橘子

1.题目描述

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

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

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

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

2.题目思路

这是通用的BFS思路，关于图和树都可以用，如二叉树的右视图，计算二叉树的层数等题目

depth = 0 # 记录遍历到第几层 while queue 非空: depth++ n = queue 中的元素个数 循环 n 次: node = queue.pop() for node 的所有相邻结点 m: if m 未访问过: queue.push(m)

3.代码及详细注释

class Solution { public: int orangesRotting(vector<vector<int>>& grid) { //1.计算腐烂橘子和好橘子，并把腐烂橘子全都入队表示0min时刻 int count=0; queue<pair<int,int>> q; int M = grid.size(); int N = grid[0].size(); for(int i = 0;i<=M-1;i++){ for(int j = 0;j<=N-1;j++){ if(grid[i][j]==1){ count++;//好橘子总数 } else if(grid[i][j]==2){ q.push({i,j}); } } } if(count==0) return 0; int round = 0;//返回的结果 int fresh = 0; while(fresh < count &&!q.empty()){//注意这个条件，最后个新鲜橘子即将被腐烂的状态，grid[i][j]=2，fresh ==count了，然后入队列被腐烂的橘子，队列不为空，还会进行一次判断. int n = q.size(); round++; while(n>0){ int i = q.front().first; int j = q.front().second; q.pop(); if(i-1>=0 &&grid[i-1][j]==1){//top //污染橘子 fresh++; grid[i-1][j]=2; q.push({i-1,j}); } if(i+1<=M-1 && grid[i+1][j]==1){//down fresh++; grid[i+1][j]=2; q.push({i+1,j}); } if(j-1>=0 && grid[i][j-1]==1){//left fresh++; grid[i][j-1]=2; q.push({i,j-1}); } if(j+1<=N-1 && grid[i][j+1]==1){//right fresh++; grid[i][j+1]=2; q.push({i,j+1}); } n--; } } if(count-fresh!=0){ return -1; } return round; } };