解题思路
本题是图上的双动点相遇问题,可拆成两部分:B 的位置是完全确定的周期序列,A 在图上自由走最短路径。核心结论:
- 玩家 B 不依赖 A,其位置只由回合
t 决定。把巡逻路径 patrolPath(一次单程)展开成循环序列:从起点走到末端后原路折返。例如 [0,1,2] 展开为 [0,1,2,1](周期 4),[5,6,7,5] 展开为 [5,6,7,5,7,6](周期 6)。一般地,cycle = patrolPath + reverse(patrolPath[1..L-2]),周期长度 C = 2L-2(L=1 时 B 原地不动,周期 1)。
- 玩家 A 每回合可移动到相邻房间或停留。因此 A 在第
t 回合能到达任意「从 startA 出发最短距离 ≤ t」的房间(先走最短路,余下的回合原地等待即可)。
- 于是 A 与 B 在第
t 回合相遇,当且仅当存在房间 u 使 B(t)==u 且 dist(startA,u) ≤ t。我们只需从小到大枚举 t(从 1 开始),找到第一个满足条件的 t 即可。
不可达(-1)判定:若 B 巡逻经过的所有房间,与 A 所在的连通分量完全没有交集(例如 A 被孤立、或 B 只在另一连通块巡逻),则永远无法相遇,直接返回 -1。