python
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1) ]
m, n = len(grid), len(grid[0])
fresh = 0
ans = 0
q = []
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
fresh += 1 # 统计新鲜橘子个数
if grid[i][j] == 2:
q.append((i, j))
while q and fresh:
ans += 1
tmp = q
q = []
for i, j in tmp:
for x, y in DIRS:
nxt_i = i + x
nxt_j = j + y
if 0 <= nxt_i < m and 0 <= nxt_j < n and grid[nxt_i][nxt_j] == 1:
fresh -= 1
grid[nxt_i][nxt_j] = 2
q.append((nxt_i, nxt_j))
return -1 if fresh else ans看示例 1：
- 统计所有初始就腐烂的橘子的位置，加到列表 q 中，现在 q=[(0,0)]。
- 初始化答案 ans=0。模拟橘子腐烂的过程，不断循环，直到没有新鲜橘子，或者 q 为空。
- 答案加一，在第 ans=1 分钟，遍历 q 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q 更新为这些橘子的位置，现在 q=[(0,1),(1,0)]。
- 答案加一，在第 ans=2 分钟，遍历 q 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q 更新为这些橘子的位置，现在 q=[(0,2),(1,1)]。
- 答案加一，在第 ans=3 分钟，遍历 q 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q 更新为这些橘子的位置，现在 q=[(2,1)]。
- 答案加一，在第 ans=4 分钟，遍历 q 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q 更新为这些橘子的位置，现在 q=[(2,2)]。
- 由于没有新鲜橘子，退出循环。
为了判断是否有永远不会腐烂的橘子（如示例 2），我们可以统计初始新鲜橘子的个数 fresh。在 BFS 中，每有一个新鲜橘子被腐烂，就把 fresh 减一，这样最后如果发现 fresh>0，就意味着有橘子永远不会腐烂，返回 −1。
作者：灵茶山艾府 链接：https://leetcode.cn/problems/rotting-oranges/solutions/2773461/duo-yuan-bfsfu-ti-dan-pythonjavacgojsrus-yfmh/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
Queue 和树形BFS的情况一样，只记录最外层的节点，已经访问过的(腐烂的)不用考虑
q and fresh 如果fresh = 0 那么q还有最外层的腐烂橘子
如果q = 0, fresh不一定为0(有橘子不能腐烂的情况)