1 題目描述

?2 解題思路

2.1 多源廣搜

使用廣搜的思想，但是和一般的廣搜不同，這里一開始的隊列不是一個元素，而是一開始就腐爛的所有橘子的坐標。

同時我們隊列里面的每一個元素是一個三元組，分別是腐爛橘子的坐標，和當前已經(jīng)經(jīng)過了的分鐘數(shù)。對于每個已經(jīng)腐爛的橘子，我們向外找一圈，將新鮮的橘子變成腐爛的橘子，然后原本新鮮位置橘子的坐標入隊列。

當隊列為空，表示所有橘子都已經(jīng)考慮過了。這時候我們看是否還有新鮮的橘子，有的話返回-1

class Solution:def orangesRotting(self, grid: List[List[int]]) -> int:lst=[]num_1=0row=len(grid)column=len(grid[0])for i in range(row):for j in range(column):if(grid[i][j]==1):num_1+=1elif(grid[i][j]==2):lst.append((i,j,0))time=0while(lst):i,j,time=lst.pop(0)for (x,y) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:if(x>=0 and x<row and y>=0 and y<column):if(grid[x][y]==1):grid[x][y]=2num_1-=1lst.append((x,y,time+1))if(num_1!=0):return(-1)else:return(time)

?2.2? while 循環(huán)

我們記當前新鮮橘子的數(shù)量為num_1，如果這個數(shù)字不為0，且連續(xù)兩分鐘內這個數(shù)字在變化，說明腐爛仍在繼續(xù)，那么就繼續(xù)循環(huán)。

每次我們遍歷當前腐爛的橘子，讓它周圍一圈的新鮮橘子也腐爛。如果一個腐爛的橘子已經(jīng)讓周圍一圈新鮮的橘子腐爛了，那我們將他的狀態(tài)設置為-1，這樣下一輪遍歷已經(jīng)腐爛的橘子的時候，這些橘子就不會再考慮了

class Solution:def orangesRotting(self, grid: List[List[int]]) -> int:num_1=0for i in grid:num_1+=i.count(1)row=len(grid)column=len(grid[0])num=0while(num_1!=0):prev_num=num_1num+=1tmp_lst=[]for i in range(row):for j in range(column):if(grid[i][j]==2):grid[i][j]=-1tmp_lst.append((i,j)) #tmp_lst中是當前這一輪腐爛的橘子，這些橘子的狀態(tài)被設置為-1，之后將不再考慮之for (i,j) in tmp_lst:for (x,y) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:if(x>=0 and x<row and y>=0 and y<column):if(grid[x][y]==1):grid[x][y]=2num_1-=1if(prev_num==num_1):return -1#如果連續(xù)兩分鐘，新鮮的橘子數(shù)量一樣，而且數(shù)量不為0，返回-1return num

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的文巾解题 994. 腐烂的橘子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。