题目重点：新增源可下降距离，删源会使距离上升，更新不能完全对称。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练0可通行/1障碍、四邻接单位步长，taxi位于可通行格；无在线可达源返回None。
- 出租车ID独立于格子，多个taxi可同格。位置移动按set_online覆盖并重算；网格固定。
解题路线
- 把全部在线taxi格距离设0同时入队，BFS一次算每格最近距离。不要为每格重复找taxi。
- 代码上下线都完整rebuild，保留正确O(RC)更新/O(1)查询基线。仅新增源可做改进BFS，删除最近源则要寻找次近源或重建；不能直接置被删格∞后局部传播旧最小值。
- 每taxi存全格距离并在每格heap可支持lazy删除，但O(T×RC)空间且过期堆需清理，静态路径遇障碍要用BFS不是DFS首次距离。规模很大需区域/近似与明确误差合同。
手动走一遍
两taxi占同格，删其中一辆该格最近距离仍0。唯一taxi下线后全部可通行格None；旧距离不能继续当真。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
class Taxis:
def __init__(self,grid):
if not grid or not grid[0] or any(len(row)!=len(grid[0]) for row in grid):raise ValueError("rectangular nonempty grid")
self.grid=grid;self.online={};self.distance=[];self.rebuild()
def set_online(self,key,cell):
r,c=cell
if not (0<=r<len(self.grid) and 0<=c<len(self.grid[0])) or self.grid[r][c]!=0:raise ValueError("not drivable")
self.online[key]=cell;self.rebuild()
def remove(self,key):
if key not in self.online:raise ValueError("unknown taxi")
del self.online[key];self.rebuild()
def rebuild(self):
rows,cols=len(self.grid),len(self.grid[0]);self.distance=[[None]*cols for _ in range(rows)];queue=deque()
for r,c in set(self.online.values()):self.distance[r][c]=0;queue.append((r,c))
while queue:
r,c=queue.popleft()
for x,y in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
if 0<=x<rows and 0<=y<cols and self.grid[x][y]==0 and self.distance[x][y] is None:
self.distance[x][y]=self.distance[r][c]+1;queue.append((x,y))
def get(self,r,c):return self.distance[r][c]
复杂度
V=RC，完整更新O(V+T)，查询O(1)，distance O(V)、在线O(T)；边数≤4V。
易错点与追问
容易失分的边界
- 单源DFS访问一次不保证最短。
- 只缓存nearestTaxi ID没有次近信息，删除时不能常数恢复。
继续深挖
- 新增taxi如何只传播严格改善区域？
- 需要nearest ID且平局固定时队列与更新比较怎样改变？
