在給定的網(wǎng)格中，每個單元格可以有以下三個值之一：
值 0 代表空單元格；
值 1 代表新鮮橘子豪筝；
值 2 代表腐爛的橘子惋嚎。
每分鐘杠氢，任何與腐爛的橘子（在 4 個正方向上）相鄰的新鮮橘子都會腐爛。
返回直到單元格中沒有新鮮橘子為止所必須經(jīng)過的最小分鐘數(shù)另伍。如果不可能鼻百，返回 -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 列）永遠(yuǎn)不會腐爛温艇，因為腐爛只會發(fā)生在 4 個正向上。
示例3：
輸入：[[0,2]]
輸出：0
解釋：因為 0 分鐘時已經(jīng)沒有新鮮橘子了堕汞，所以答案就是 0 勺爱。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/rotting-oranges
class Solution(object):
def orangesRotting(self, grid):
#判斷第0分鐘就是最后結(jié)果的情況
flag = 1
for i in range(len(grid)):
for j in range (len(grid[0])):
if grid[i][j] == 1:
flag = 0
if flag == 1:
return 0
my_queque = []
result = 0
#將初始的壞橘子入隊
for i in range(len(grid)):
for j in range (len(grid[0])):
if grid[i][j] == 2:
my_queque.append((i,j))
#對隊列中的壞橘子，依次出隊讯检，并讓其感染相鄰的橘子琐鲁，將新感染的橘子入隊，直到隊列為空
while my_queque:
count = len(my_queque)
result += 1
for i in range(count):
cur = my_queque.pop(0)
if cur[0]-1 >= 0 and grid[cur[0]-1][cur[1]] == 1:
grid[cur[0]-1][cur[1]] = 2 if grid[cur[0]-1][cur[1]] == 1 else 0
my_queque.append((cur[0]-1,cur[1]))
if cur[0]+1 <len(grid) and grid[cur[0]+1][cur[1]] == 1:
grid[cur[0]+1][cur[1]] = 2 if grid[cur[0]+1][cur[1]] == 1 else 0
my_queque.append((cur[0]+1,cur[1]))
if cur[1] -1 >= 0 and grid[cur[0]][cur[1]-1] == 1:
grid[cur[0]][cur[1]-1] = 2 if grid[cur[0]][cur[1]-1] == 1 else 0
my_queque.append((cur[0],cur[1]-1))
if cur[1]+1 <len(grid[0]) and grid[cur[0]][cur[1]+1] == 1:
grid[cur[0]][cur[1]+1] = 2 if grid[cur[0]][cur[1]+1] == 1 else 0
my_queque.append((cur[0],cur[1]+1))
#如果有未感染的橘子人灼，返回 -1
for i in range(len(grid)):
if 1 in grid[i]:
return -1
#否則围段，返回 result-1（因為最后一次沒有新感染的橘子，但是result+1）
return result-1
