火炬节点功率传播：最近火炬的多源BFS

题目重点：火炬提供16功率，按边距离衰减，先写清衰减合同。

题意与假设

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

训练合同：无向等长wire，每跨一边减1，功率下界0；多个火炬取最大传播功率，不叠加。
源只给16与distance decay，具体率/是否加和未公开；若正式题不同，算法须调整。

解题路线

多个等强火炬同时distance0入队。多源BFS首次访问点给最近火炬距离，所以power=max(0,16−distance)。
达到距离16以后传播功率0，可不继续扩展；所有未达或过远点也为0。重复火炬去重，孤立点有火炬则16。
加权wire要Dijkstra，火炬强度不同则可用最大功率优先队列松弛；若叠加来自所有火炬贡献，最近一个不够。

手动走一遍

链0−1−2−3，火炬0/3，距离[0,1,1,0]，功率[16,15,15,16]。两强度16火炬邻同点，max规则仍16而非32。

Python 参考实现

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

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

from collections import deque


def power_levels(n,edges,torches,strength=16):
    if n<0 or strength<0:raise ValueError("nonnegative n and strength required")
    graph=[set() for _ in range(n)]
    for u,v in edges:
        if not 0<=u<n or not 0<=v<n:raise ValueError("invalid edge")
        graph[u].add(v);graph[v].add(u)
    distance={}
    for u in torches:
        if not 0<=u<n:raise ValueError("invalid torch")
        distance[u]=0
    q=deque(distance)
    while q:
        u=q.popleft()
        if distance[u]>=strength:continue
        for v in graph[u]:
            if v not in distance:distance[v]=distance[u]+1;q.append(v)
    return [max(0,strength-distance[u]) if u in distance else 0 for u in range(n)]

复杂度

O(V+E)时间/O(V+E)空间含图。固定衰减半径可减少实际遍历但仍需读输入边。

易错点与追问

容易失分的边界

把通达性当功率，所有可达点都赋16会忽略衰减。
Manhattan距离只适用特定网格且无阻碍最短距离合同，不适用任意wire图。

继续深挖

若edge距离非整数，怎样决定功率比较与精度？
网络动态加火炬/移火炬时哪些更新可以增量，删除为何更难？