题目重点：依据两篇 Pin/Board 电面，明确共享看板计一步、判断连通、Pin 最短距离及任意两 Board 的最短 Pin 距离。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 两个 pin 同属一个 board 时距离为 1；不同 board 可经共享 pin 串联，自己到自己距离 0。
- “相关”训练版解释为存在任意共享 board 路径；若面试官只把同板视为相关，判定规则须改。Board→Board 题取两组 pin 任意一对的最小 pin 距离，共享 pin 时为 0。
- 不存在的 pin/board 或不可达返回 -1；pin 名称在各 board 上指同一个实体。
解题路线
- 从 board→pins 反向建立 pin→boards 索引，不提前在大 board 内建所有 pin pair，以免平方级边数。
- Pin→Pin BFS 从起点出发，每扩展一个尚未访问的 board，就把其所有 pin 作为下一层；一次查询中每块 board 最多扩展一次。
- Board→Board 把起始 board 的所有 pin 以距离 0 同时入队，碰到目标 board 的任意 pin 即返回。
- 多次查询时可缓存同源 BFS 距离，但若成员关系和可见性会改变，缓存键与失效必须包含图版本和权限条件。
手动走一遍
旅游={山,湖,旅社}，装饰={房子,石塘,旅社}，涂鸦={毕加索,湖}。山→湖 同板距离 1；山→房子 经旅社距离 2；石塘→毕加索 可经旅社、湖走 3。旅游与装饰共享旅社，Board→Board 最小距离为 0。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Pin distance counts shared-board hops, not bipartite edges."""
from collections import defaultdict, deque
class PinBoardGraph:
def __init__(self, boards: dict[str, list[str]]):
self.boards = {board: set(pins) for board, pins in boards.items()}
self.pin_to_boards = defaultdict(set)
for board, pins in self.boards.items():
for pin in pins:
self.pin_to_boards[pin].add(board)
def pin_distance(self, start: str, target: str) -> int:
if start not in self.pin_to_boards or target not in self.pin_to_boards:
return -1
return self._bfs({start}, {target})
def board_distance(self, first: str, second: str) -> int:
if first not in self.boards or second not in self.boards:
return -1
return self._bfs(self.boards[first], self.boards[second])
def _bfs(self, starts: set[str], targets: set[str]) -> int:
if not starts or not targets:
return -1
queue = deque((pin, 0) for pin in starts)
visited_pins = set(starts)
visited_boards = set()
while queue:
pin, distance = queue.popleft()
if pin in targets:
return distance
for board in self.pin_to_boards[pin]:
if board in visited_boards:
continue
visited_boards.add(board)
for neighbor in self.boards[board]:
if neighbor not in visited_pins:
visited_pins.add(neighbor)
queue.append((neighbor, distance + 1))
return -1
复杂度
设成员关系总数 E、Pin 数 P、Board 数 B，建双向索引 O(E) 时间和空间；每次 BFS 最坏 O(P+B+E)，队列 O(P)，每个 board 在一次查询只展开一次。直接将每个 board 内 pins 两两连边可能达到 O(Σ|board|²)。
易错点与追问
容易失分的边界
- 直接把 bipartite Pin→Board→Pin 两条边算成距离 2，与示例距离 1 冲突。
- Board→Board 从单个任意 pin 出发，漏掉更短 pair。
- 大 board 完全连 clique 导致内存暴涨。
- 把隐私过滤当作题目条件；它只是生产延伸，不应冒充该场题面。
继续深挖
- 海量重复查询时，如何按热点起点缓存 BFS 结果？
- board 新增/删除 pin 后，预计算距离如何失效？
- 若只允许用户可见的 Pin 作为中转，遍历怎样加入权限检查？
