本文主要是介绍Leetcode 994. 腐烂的橘子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
心路历程：
一开始以为和刚做过的岛屿问题很像，只不过是把岛屿问题换成BFS去做，然后再加上一些计数的规则。结果做完后发现只能通过一半左右的测试用例，发现有一个逻辑错误在于，当腐烂的橘子位于两端时，可以共同腐蚀从而加速进程。而依次遍历所有grid再分别去BFS的顺序思路很明显就不行了。从网上搜素了一下相关的解题思路，发现可以按照多点开花的BFS来做这道题，感觉这样更有图的味道了。
这道题对我来说其实是一道困难题。
注意的点：
1、BFS中队列的本质是一层一层，但是并不一定根结点只有一个，所以可以先把所有腐烂的根结点拿到放到队列中再去一层层地遍历。
2、只有当某一层至少有一个好橘子被腐蚀时，才应该计数+1，否则代表这一圈全是坏橘子不需要占用腐蚀时间。
3、本题可以通过判断全部腐蚀完成后看好橘子是否还剩下来判断是否全部腐蚀完成，否则就是有孤立的橘子。并不一定非要按照岛屿问题那样遍历出所有孤立的岛屿才计数。
4、注意本题要求的是整数类型的1，不是字符串类型的“1”。
5、if else后的语句只有一行时写到一起更简洁。
6、发现队列这种数据结构在用于搜索时可以作为’假并行‘，但是递归的DFS不行，想了想用一个栈实现的DFS好像也不能做到这种类似的并行深度优先搜索。本质还是在于队列的顺序在即使有不同根节点时也是可以累加放到一起同时操作的。
解法：BFS+多点并行处理
class Solution:def orangesRotting(self, grid: List[List[int]]) -> int:# BFS + 并行同时仿真扩散from collections import dequem, n = len(grid), len(grid[0])dxy = [(0,1), (0,-1), (1,0), (-1,0)]bads = deque([])goodnum = 0for i in range(m): # 获取所有坏橘子的坐标和好橘子的数量for j in range(n):if grid[i][j] == 1: goodnum += 1elif grid[i][j] == 2: bads.append((i,j))if goodnum == 0: return 0time = 0while bads: # 每一层只传播好橘子，入队规则：只有好橘子才入队l = len(bads)level = 0 # 判断这一层是否有好橘子被感染for _ in range(l):bx, by = bads.popleft()for dx, dy in dxy:newx, newy = bx + dx, by + dyif 0 <= newx <= m-1 and 0 <= newy <= n-1 and grid[newx][newy] == 1:bads.append((newx, newy))level = 1grid[newx][newy] = 2goodnum -= 1time += levelif goodnum != 0: # 这一点很关键，与前面事先统计了好橘子的数量相呼应。time = -1return time
这篇关于Leetcode 994. 腐烂的橘子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
