Google OA 面试真题解析：无线消息传播与路由器可达性

Network of routers: each router has an (x, y) coordinate.

A message can be broadcast from one router to another if the Euclidean distance between them is within wireless range.

Given a source router and a destination router, determine whether the message will reach the destination from the source.

Example:

A(0, 0), B(0, 8), C(0, 17), D(11, 0)
Wireless range = 10
Start = A

In this example, A can send a message to B, but cannot directly send to C or D.

这道题本质上是在一个由路由器组成的图中判断消息是否可达：每个路由器都有二维坐标，如果两点之间的欧氏距离不超过无线范围，就可以建立一条边。求从源点到目标点是否能收到消息，通常可以把所有路由器看成图节点，用 BFS 或 DFS 进行连通性搜索；如果还需要处理“广播并关闭”这类状态变化，则要注意访问标记和传播顺序。题目重点在于正确建图、距离判断以及用图遍历判断可达性。