LeetCode0994.RottingOranges腐烂的橘子【Easy】【Python】【BFS】问题LeetCode在给定的网格中，每个单元格可以有三个值之一：值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-directionally.Example3:Input:[[0,2]]Output:0Explanation:由于在第0分钟已经没有新鲜的橘子了，答案就是0。注：1<=grid.length<=101<=grid[0].length<=10grid[i][j]只是0、1或2。问题是在给定的网格中，每个单元格可以具有以下三个值之一：值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<=101<=grid[0]。length<=10grid[i][j]只有0、1、2个ideaBFS先统计新鲜橙子的个数，把烂橙子的个数放入队列q。遍历q，每次弹出队列第一个元素，判断周围有没有新鲜的橙子，变成烂的，同时加入队列q，fresh减1。当q为空时，表示全部腐烂。每次遍历都要判断是否还有剩余的新鲜橙子，如果没有剩余，则直接返回minute。遍历结束时还需要判断是否还有新鲜的橙子（防止出现例2那种永远不会腐烂的橙子的情况）。时间复杂度：O(n*m)，其中n是行数，m是列数。空间复杂度：O(n*m)，其中n是行数，m是列数。Python3代码类解决方案：deforangesRotting(self,grid:List[List[int]])->int:n,m=len(grid),len(grid[0])fresh=0q=[]#countfresh橙子和排队腐烂的橙子foriinrange(n):forjinrange(m):ifgrid[i][j]==1:fresh+=1elifgrid[i][j]==2:q.append((i,j))如果新鲜==0:返回0dirs=[(0,1),(0,-1),(-1,0),(1,0)]minute=0#bfswhileq:iffresh==0:returnminutesize=len(q)foriinrange(size):x,y=q.pop(0)fordindirs:nx,ny=x+d[0],y+d[1]如果nx<0或nx>=n或ny<0或ny>=m或grid[nx][ny]!=1:继续grid[nx][ny]=2q.append((nx,ny))fresh-=1minute+=1iffresh!=0:return-1代码地址github链接
