题目描述:
题解:
广度优先搜索
基本思路:
1.创建一个队列myq,初始时加入grid中值为2的位置坐标。
2.每次从myq中取出一个坐标(posx,posy),依次判断该位置上下左右四个相邻位置的grid值是否为1,如果是1,将该相邻位置加入myq,并将grid中该位置的值修改为2,表示已经被处理。
3.由于此题中需要计算处理完成需要的时间,所以第二步实现的时候需要做一点处理,不直接把坐标位置加入myq,而是先把同时被腐烂的所有节点位置(可能被相同或不同的已经腐烂的橘子影响)保存在一个队列中,然后再将该队列加入myq,每加入一个队列,times+1。
4.队列为空表示处理完成,腐烂的传播过程完成,橘子已经全部腐烂或者已经没有可以被影响的橘子了。
5.统计处理完成后的grid,如果还存在值为1的节点,则表示存在无法被腐烂的橘子返回-1,否则返回times。
class Solution(object):
def orangesRotting(self, grid):
myq = deque()
times = 0
directions = [(0,-1),(0,1),(-1,0),(1,0)]
row = len(grid)
col = len(grid[0])
mylist = []
for i in range(row):
for j in range(col):
if grid[i][j] == 2:
mylist.append((i,j))
myq.append(mylist)
while myq:
list1 = myq.popleft()
list2 = []
while list1:
posx,posy = list1[0]
list1.pop(0)
for dx,dy in directions:
nx = posx+dx
ny = posy+dy
if 0<=nx



