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(vectorvectorint grid) { //1.计算腐烂橘子和好橘子并把腐烂橘子全都入队表示0min时刻 int count0; queuepairint,int q; int M grid.size(); int N grid[0].size(); for(int i 0;iM-1;i){ for(int j 0;jN-1;j){ if(grid[i][j]1){ count;//好橘子总数 } else if(grid[i][j]2){ q.push({i,j}); } } } if(count0) return 0; int round 0;//返回的结果 int fresh 0; while(fresh count !q.empty()){//注意这个条件最后个新鲜橘子即将被腐烂的状态grid[i][j]2fresh count了然后入队列被腐烂的橘子队列不为空还会进行一次判断. int n q.size(); round; while(n0){ int i q.front().first; int j q.front().second; q.pop(); if(i-10 grid[i-1][j]1){//top //污染橘子 fresh; grid[i-1][j]2; q.push({i-1,j}); } if(i1M-1 grid[i1][j]1){//down fresh; grid[i1][j]2; q.push({i1,j}); } if(j-10 grid[i][j-1]1){//left fresh; grid[i][j-1]2; q.push({i,j-1}); } if(j1N-1 grid[i][j1]1){//right fresh; grid[i][j1]2; q.push({i,j1}); } n--; } } if(count-fresh!0){ return -1; } return round; } };