20260708-迷宫相遇（N0044）- 算法机考高频题型 · 华为OD / BFS题解 | AlgoMooc

N0044. 20260708-迷宫相遇

困难

通过率 67% · 提交 9 · 通过 6

华为ODBFS

概念速查：BFS 与 DFS 的区别是什么

算法机考高频题型改编 · 聚焦「华为OD / BFS」 · 难度：困难

一个封闭迷宫，有 n 个房间（编号 0 到 n-1），相邻房间由双向门连接。玩家 A 自由移动，玩家 B 沿给定路径来回巡逻。求玩家 A 的最优移动策略，使得与玩家 B 在最少回合相遇。注意：A 和 B 初始出发点不同。规则：

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

这类题属于算法机考高频题型中「华为OD / BFS」方向的高频题型，通常考察对「华为OD / BFS」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

输入描述

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

输出描述

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

示例

示例 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

输出示例

说明：

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

示例 3

时间限制 1000 ms · 内存限制 256 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

问小欧 · 图解算法年卡¥99 开通 →

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

from typing import List

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# @param n int 房间数量
# @param edges List[List[int]] 房间连接关系
# @param startA int A的初始房间编号
# @param patrolPath List[int] B的巡逻路径（一次单程）
# @return int A和B相遇的最小回合次数，若无法相遇返回-1
class Solution:
    def minMeetRounds(self, n: int, edges: List[List[int]], startA: int, patrolPath: List[int]) -> int:
        # 请在此编写代码
        pass

# 以下内容为LeetCode核心代码模式转为ACM模式所需代码
# 请在algomooc oj上直接使用，在实际考试中无需编写

def main():
    n = int(input().strip())

    edges_str = input().strip()
    edges = []
    # 判断边关系输入是否为空，若为空字符串则 edges 保持为空列表
    if edges_str:
        for pair in edges_str.split():
            u, v = map(int, pair.split(','))
            edges.append([u, v])

    startA = int(input().strip())

    patrolPath_str = input().strip()
    # 判断巡逻路径输入是否为空，若为空则设为包含一个0的列表（但题目保证至少一个元素）
    if patrolPath_str:
        patrolPath = list(map(int, patrolPath_str.split(',')))
    else:
        patrolPath = [0]

    sol = Solution()
    print(sol.minMeetRounds(n, edges, startA, patrolPath))

if __name__ == "__main__":
    main()

from typing import List

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# @param n int 房间数量
# @param edges List[List[int]] 房间连接关系
# @param startA int A的初始房间编号
# @param patrolPath List[int] B的巡逻路径（一次单程）
# @return int A和B相遇的最小回合次数，若无法相遇返回-1
class Solution:
    def minMeetRounds(self, n: int, edges: List[List[int]], startA: int, patrolPath: List[int]) -> int:
        # 请在此编写代码
        pass

# 以下内容为LeetCode核心代码模式转为ACM模式所需代码
# 请在algomooc oj上直接使用，在实际考试中无需编写

def main():
    n = int(input().strip())

edges_str = input().strip()
    edges = []
    # 判断边关系输入是否为空，若为空字符串则 edges 保持为空列表
    if edges_str:
        for pair in edges_str.split():
            u, v = map(int, pair.split(','))
            edges.append([u, v])

startA = int(input().strip())

patrolPath_str = input().strip()
    # 判断巡逻路径输入是否为空，若为空则设为包含一个0的列表（但题目保证至少一个元素）
    if patrolPath_str:
        patrolPath = list(map(int, patrolPath_str.split(',')))
    else:
        patrolPath = [0]

sol = Solution()
    print(sol.minMeetRounds(n, edges, startA, patrolPath))

if __name__ == "__main__":
    main()

写完代码点「提交」，将对全部测试用例判题。

输入描述

输出描述

示例

我的提交