Meta 墙与门：多源BFS求最近门距离

题目重点：从全部门同时扩散，给每个空房填写最近门距离，保留不可达与墙。

题意与假设

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

训练−1墙、0门、2^31−1空房，4邻接每步1；原地修改rooms，无门/不可达保留EMPTY。
输入已有距离不是本例合法初始化状态，若需要更新旧距离需重新定义处理。

解题路线

初始化将所有门以距离0入同一queue，不为每个房间分别BFS，也不按门顺序完成一个搜索再下一个。
出队邻居仍EMPTY时写当前距离+1并入队。首次赋值后不再访问，使每房只处理一次；门不被其他门路径覆盖。
把所有门视作虚拟超级源的零距离起点，BFS分层保证第一次到达房间就是任一门最短距离。墙始终不参与图。
无门时queue空结果不变；多门距离tie只需数值相同，不需要选择门身份。若返回最近门ID，保留来源并明确tie。

手动走一遍

一行[0,EMPTY,EMPTY,0]结果[0,1,1,0]；[0,−1,EMPTY]最后房不可达。先从左门填完整再禁止更新会把第三格错写2而非右门距离1。

Python 参考实现

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

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

from collections import deque

EMPTY=2**31-1

def fill_gate_distances(rooms):
    """-1 wall, 0 gate, EMPTY room; four neighbors, mutate rooms in place."""
    if not rooms or not rooms[0]:return rooms
    rows,cols=len(rooms),len(rooms[0]);queue=deque()
    if any(len(row)!=cols or any(v not in (-1,0,EMPTY) for v in row) for row in rooms):raise ValueError('invalid rooms')
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c]==0:queue.append((r,c))
    while queue:
        r,c=queue.popleft()
        for dr,dc in ((-1,0),(1,0),(0,-1),(0,1)):
            rr,cc=r+dr,c+dc
            if 0<=rr<rows and 0<=cc<cols and rooms[rr][cc]==EMPTY:
                rooms[rr][cc]=rooms[r][c]+1;queue.append((rr,cc))
    return rooms

复杂度

O(RC)时间、O(RC)最坏队列，修改已有矩阵不另存距离表。每房单独搜索最坏O((RC)²)，多源只完整遍历一次。

易错点与追问

容易失分的边界

只入一个门导致结果并非最近门。
把EMPTY房直接改为visited1却丢掉真正距离。

继续深挖

边带非负不同权重时，全部门共同初始化Dijkstra。
门新增/删除时是否能局部更新？删除可能使大范围距离失效，需保留更多结构或重算。