leetcode---994腐烂橘子
994-腐烂的橘子
在给定的网格中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
image.png
方法1：BFS+数组
这个可以使用广度优先搜索（BFS)方法，BFS 可以看成是层序遍历。从某个结点出发，BFS 首先遍历到距离为 1 的结点，然后是距离为 2、3、4…… 的结点。因此，BFS 可以用来求最短路径问题。BFS 先搜索到的结点，一定是距离最近的结点。
再看看这道题的题目要求：返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。翻译一下，实际上就是求腐烂橘子到所有新鲜橘子的最短路径。可以联系树来思考，每一个结点作为已经感染的橘子，它的子节点表示它四周的橘子。然后一层一层的进行感染
1.首先分别将腐烂的橘子和新鲜的橘子保存在两个集合中；
-
模拟广度优先搜索的过程，while 新鲜集合，如果腐烂集合为空，直接返回-1，如果不为空，方法是判断在每个腐烂橘子的四个方向上是否有新鲜橘子，如果有就腐烂它。每腐烂一次时间加 1，并剔除新鲜集合里腐烂的橘子；
-
当橘子全部腐烂时结束循环。
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
row = len(grid)
col = len(grid[0])
rotten = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 2} # 腐烂集合
fresh = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 1} # 新鲜集合
time = 0
while fresh:
if not rotten: return -1
rotten = {(i + di, j + dj) for i, j in rotten for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)] if (i + di, j + dj) in fresh} # 即将腐烂的如果在新鲜的集合中，就将它腐烂
fresh -= rotten # 剔除腐烂的
time += 1
return time
复杂度分析
时间复杂度：O(mn)O(mn)。
空间复杂度：O(mn)O(mn)。
方法2：也是BFS方法， BFS +队列
队列中只让腐烂的橘子入队stack,同时初始化每个橘子的参观状态为False；
记录腐烂的方向数组
判断增减方向后的橘子边界范围，是否参观，是不是新鲜的
如果是出队，让当前腐烂橘子四周的新鲜橘子都变为腐烂，即 grid[y_new][x_new] = 2。同时visist=True
用 minute 记录腐烂的持续时间，每一层的橘子在内一层的橘子的腐烂时间基础之上自增 1，代表时间过了 1 分钟。
最后检查网格中是否还有新鲜的橘子有，返回 -1 代表 impossible。没有则返回 minute。
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
# 网格的长，宽
m, n = len(grid), len(grid[0])
# 网格每一个坐标的访问状态
visit = [[False] * n for y in range(m)]
# 找出最开始时，网格中所有坏橘子的坐标
stack = [[y,x] for y in range(m) for x in range(n) if grid[y][x]==2]
# 坏橘子传染好橘子的四个方向，上下左右
direction = [[-1,0], [1,0], [0,-1], [0,1]]
# 初始时间
minute = 0
# 开始坏橘子传染好橘子的循环，直到没有好橘子可以被传染
while True:
# 初始化一个stack_next，把这一轮变坏的橘子装进里面
stack_next = []
# 开始对坏橘子进行审查，主要是看上下左右有没有好橘子
while stack:
# 拿出坏橘子的坐标点
y, x = stack.pop()
# 再看坏橘子上下左右的坐标对应的坐标
for d in direction:
y_new, x_new = y + d[0], x + d[1]
# 如果坐标在网格范围内，而且坐标没有被访问过，且这个坐标确实有个好橘子
if -1 < y_new < m and -1 < x_new < n and not visit[y_new][x_new] and grid[y_new][x_new] == 1:
# 观察慰问一下这个好橘子，表示已经访问过了
visit[y_new][x_new] = True
# 告诉这个好橘子，你已被隔壁的坏橘子感染，现在你也是坏橘子了
grid[y_new][x_new] = 2
# 放进stack_next里面，集中管理，精准隔离，方便排查下一轮会变坏的橘子
stack_next.append([y_new, x_new])
# 如果橘子们都检查完了发现再无其他坏橘子，终止循环，宣布疫情结束
if not stack_next: break
# 把这一轮感染的坏橘子放进stack里，因为我们每一轮都是从stack开始搜索的
stack = stack_next
# 看来橘子们还没凉透，来，给橘子们续一秒，哦不，续一分钟
minute += 1
# 经过传染，审查，隔离的循环后，如果还有好橘子幸存，返回-1宣布胜利，否则返回橘子们的存活时间
return -1 if ['survive' for y in range(m) for x in range(n) if grid[y][x]==1] else minute
时间复杂度
空间复杂度
