leetcode 994. 腐烂的橘子 python

题目描述：

题解：

广度优先搜索

基本思路：

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 = 0directions = [(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+dxny = posy+dyif 0<=nx 
 
 
 
 
                        

                        

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！