Amazon Coding：Rotten Oranges，为什么所有源同时入队？

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 0空格、1新鲜、2已烂，四邻接每分钟传播一步；同时传播，空格不可通行。
• 返回全部新鲜腐烂最少分钟，无新鲜0，任何不可达新鲜-1；输入不修改。

解题路线

1. 把全部初始2以time=0入同一BFS队列，统计fresh。发现新鲜邻格立刻标2且fresh--，入队time+1。
2. 多源BFS每个点首次到达距离等于到任意源的最短距离，因此最晚腐烂时间是所有可达新鲜格距离最大值。若队列空后fresh仍>0，证明没有传播路径。
3. 不能逐源单独BFS后相加时间，那会将同时过程错串行；逐源取距离最小虽可正确，却重复探索很慢。
4. 发现时就标记，防止两源在同分钟对同新鲜格重复扣计数。无需人为每次外层循环加一分钟后再修正无新鲜边界。

手动走一遍

训练[[2,1,1],[1,1,0],[0,1,1]]结果4；[[1]]为-1；[[2,0]]为0。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import deque


def rotting_minutes(grid):
    if not grid:return 0
    width=len(grid[0])
    if any(len(row)!=width for row in grid) or any(v not in (0,1,2) for row in grid for v in row):
        raise ValueError("expected rectangular 0/1/2 grid")
    state=[row.copy() for row in grid]
    queue=deque()
    fresh=0
    for r,row in enumerate(state):
        for c,value in enumerate(row):
            if value==2:queue.append((r,c,0))
            elif value==1:fresh+=1
    elapsed=0
    while queue:
        r,c,time=queue.popleft()
        for nr,nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
            if 0<=nr<len(state) and 0<=nc<width and state[nr][nc]==1:
                state[nr][nc]=2
                fresh-=1
                elapsed=time+1
                queue.append((nr,nc,time+1))
    return elapsed if fresh==0 else -1

复杂度

O(RC)时间与空间，包含不修改输入的拷贝；每格至多首次腐烂入队一次。

易错点与追问

容易失分的边界

• 依次运行各源并累加时间。
• 出队才标记导致fresh重复减。
• 没有新鲜也返回1。

继续深挖

• 传播速度按格不同为何改Dijkstra？
• 多种污染不同规则能否一队处理？
• 要返回每个格子的传播时刻？