2026 华为OD机试真题 7月8日华为OD上机新系统考试真题 200 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

一个封闭迷宫，有 n 个房间（编号 0 到 n−1），相邻房间由双向门连接。玩家 A 自由移动，玩家 B 沿给定路径来回巡逻。求玩家 A 的最优移动策略，使得与玩家 B 在最少回合相遇。

注意： A 和 B 初始出发点不同。

2026 华为OD机试真题 7月8日华为OD上机新系统考试真题 200 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

规则

• 每回合，A 可以移动到相邻房间或停留在当前房间
• B 按给定路径径循环移动：从起点开始，每回合移动到路径下一个位置，到达末端后折返，回到起点后再折返，如此循环往复。间内无需停留，如：单程 [0,1,2]，完整路径为 [0,1,2,1,0,1,…]。初始在 0 点，第一回合进到 1…
• A 和 B 某回合结束后在同一房间，视为相遇

输入描述

输入为一行字符串，格式为：n,edges,startA,patrolPath

• 第一个值：n，房间数量，1<n<100
• 第二个值：edges，房间连接关系，例如 [[0,1],[1,2],[2,3],[3,4]]，双向连通，空数组表示无元连接
• 第三个值：startA，A 的初始房间编号
• 第四个值：patrolPath，B 的巡逻路径（一次单程），例如 [0,1,2] 表示 B 从 0 出发，经过 1 到达 2，然后原路返回，路径为 [0,1,2,1,0,1,2,…]。至少有一个元素，表示 B 原地不动

输出描述

类型：int

A 和 B 相遇的最小回合次数，若无法相遇返回 −1

示例1

输入

5,[[0,1],[1,2],[2,3],[3,4]],4,[0,1,2,3,4]

输出

2

说明

线性迷宫相向移动

示例2

输入

8,[[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,5]],0,[5,6,7,5]

输出

6

说明

• 有环的迷宫，B 的一轮往返路径为 5,6,7,5,7,6,5，
• A 移动到 5 后停留
• 一回合相遇

示例3

输入

5,[[0,1],[1,2],[2,3],[3,4]],3,[0,1,2]

输出

-1

说明

无路径相连，无法相遇

示例4

输入

3,[],0,[1]

输出

-1

说明

迷宫房间都不连接，无法相遇

示例5

输入

3,[[0,2]],0,[2]

输出

1

说明

B 在出发点不动，A 移动到 B 出发点相遇

解题思路

核心思想

玩家 A 可以在任意回合选择最佳策略到达任意距其起点步数 ≤ t 的房间，所以只需枚举回合 t，找到 B 在 t 回合所在房间 u 满足 dist[u] ≤ t 的最小 t，即为最早相遇回合。

算法步骤

1. BFS 求 A 到所有房间的最短路：以 startA 为源点 BFS，得到 dist[u] 表示 A 到达房间 u 所需的最少回合数
2. 构造 B 的循环巡逻序列：将 B 的单程路径 patrolPath 展开成循环：
   • 单程 [0,1,2] 展开为 [0,1,2,1,0,1,2,1,...]
   • 完整循环 = 单程 + 单程的中间段反转（patrolPath[-2:0:-1]）
3. 枚举回合求最早相遇：从 t=1 开始枚举，B 在第 t 回合位于 cycle[t % C]，若 dist[u] ≤ t 则相遇成功，返回 t
4. 不可达处理：若 B 巡逻路径上所有房间都不可达（dist[u] = INF），返回 -1

复杂度分析

• 时间复杂度：O(N + M + C·T)，其中 C 为循环长度，T 为相遇回合上限
• 空间复杂度：O(N