黑盒距离点集可达：隐式图搜索与二次查询边界

题意与假设

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

• points按索引区分身份，distance非负黑盒；代码甚至适用于非对称距离的有向图。
• 不假设欧氏度量或三角不等式，不自动用KD树。start==target按零步路径可达。

解题路线

1. BFS只对出队u与尚未发现v查询，命中则标记并入队。无需预建全部邻接，达到target可提前停。
2. 每对u/v最多在u扫描时查一次，单次搜索不需要O(n²)缓存。多次同点集查询可缓存距离，但内存随已查pair增加且数据版本改变要失效。
3. 任意黑盒可让唯一连接边藏在最后一个未查pair，最坏仍要二次查询。只有已确认低维欧氏距离才可用网格或空间索引筛邻域；高维/高密度仍可能退化。

手动走一遍

r5，距离恰5不连，4.999连；不能把<替成≤。A到B近，B到C近，可A到C远，路径仍可达；不应只查询start到target。

Python 参考实现

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

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

from collections import deque

def reachable(points,start,target,radius,distance):
    n=len(points)
    if not (0<=start<n and 0<=target<n):raise ValueError("unknown endpoint")
    seen={start};queue=deque([start])
    while queue:
        u=queue.popleft()
        if u==target:return True
        for v in range(n):
            if v not in seen and distance(points[u],points[v])<radius:
                seen.add(v);queue.append(v)
    return False

复杂度

最坏O(n²)距离调用，时间再乘单调用成本；队列/seen O(n)，点输入另计。多查询缓存O(Q)已查pair空间。

易错点与追问

容易失分的边界

• 浮点近阈值是否设容差会改变题意。
• 对未知metric使用坐标网格会漏满足黑盒距离的邻居。

继续深挖

• 对静态多源查询，连通分量预处理在何种对称合同下有效？
• 距离服务有费用和限流时如何预算与并行但保留正确性？