Status
Development
Support
- 京ICP备2025123107号-1
- Worker 0, 48ms
- Powered by Hydro v5.0.0-beta.18 Community
本题是图上的双动点相遇问题，可拆成两部分：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）。t 回合能到达任意「从 startA 出发最短距离 ≤ t」的房间（先走最短路，余下的回合原地等待即可）。t 回合相遇，当且仅当存在房间 u 使 B(t)==u 且 dist(startA,u) ≤ t。我们只需从小到大枚举 t（从 1 开始），找到第一个满足条件的 t 即可。不可达（-1）判定：若 B 巡逻经过的所有房间，与 A 所在的连通分量完全没有交集（例如 A 被孤立、或 B 只在另一连通块巡逻），则永远无法相遇，直接返回 -1。
一个封闭迷宫，有 n 个房间（编号 0 到 n−1），相邻房间由双向门连接。玩家 A 自由移动，玩家 B 沿给定路径来回巡逻。求玩家 A 的最优移动策略，使得与玩家 B 在最少回合相遇。
注意： A 和 B 初始出发点不同。
| 参数 | 类型 | 说明 |
|---|---|---|
| n | int | 房间数量，1<n<100 |
| edges | int型二维数组 | 房间连接关系，例如 [[0,1],[1,2],[2,3],[3,4]]，双向连通，空数组表示无元连接 |
| startA | int | A 的初始房间编号 |
| patrolPath | int[] | B 的巡逻路径（一次单程），例如 [0,1,2] 表示 B 从 0 出发，经过 1 到达 2，然后原路返回，路径为 [0,1,2,1,0,1,2,…]。至少有一个元素，表示 B 原地不动 |
类型：int
A 和 B 相遇的最小回合次数，若无法相遇返回 −1
输入
5,[[0,1],[1,2],[2,3],[3,4]],4,[0,1,2,3,4]
输出
2
说明
线性迷宫相向移动
输入
8,[[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,5]],0,[5,6,7,5]
输出
6
说明
输入
5,[[0,1],[1,2],[3,4]],3,[0,1,2]
输出
-1
说明
无路径相连，无法相遇
输入
3,[],0,[1]
输出
-1
说明
迷宫房间都不连接，无法相遇
输入
3,[[0,2]],0,[2]
输出
1
说明
B 在出发点不动，A 移动到 B 出发点相遇
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册