# 机考复盘 题意根据考场回忆整理可能与原题存在细节差异。## 题目描述有一个地图由 N 个房间组成房间之间通过 M 条双向通道连接。给定- 房间数量 N- 双向通道 edges- A 的初始房间位置- B 的活动轨迹数组。其中- A 可以在地图中自由移动每一回合最多移动一条边也可以选择停留- B 只能按照给定的轨迹移动。例如B 的轨迹为[1,2,3]表示 B 的移动规律为1 - 2 - 3 - 2 - 1 - 2 - 3 - ...求 A 和 B 最少经过多少回合可以在同一个房间相遇。如果永远无法相遇返回 -1。---## 输入描述第一行N M表示- N房间数量- M通道数量接下来 M 行u v表示房间 u 和房间 v 之间存在一条双向通道。随后输入startA表示 A 的起始房间。最后输入 B 的轨迹b1 b2 ... bk表示 B 的移动路线。---## 输出描述输出一个整数- 最早相遇的回合数- 如果无法相遇输出 -1。---## 示例### 输入房间5边0 11 22 33 4图结构0 - 1 - 2 - 3 - 4AstartA 0B[4,3,2]B 的运动轨迹4 - 3 - 2 - 3 - 4 - 3 - 2 ...### 分析A 到各房间的最短距离dist[0] 0dist[1] 1dist[2] 2dist[3] 3dist[4] 4模拟 B| 时间 | B位置 | A是否可到达 ||----|----|----||0|4|需要4步不行||1|3|需要3步不行||2|2|需要2步可以|答案2---# 解题思路## 1. 建图房间和通道组成一个无权图。使用邻接表graph[i] 与房间 i 相连的房间---## 2. BFS 求 A 到所有房间的最短距离因为 A 每回合只能移动一条边所以使用 BFSdist[i]表示A 到房间 i 最少需要多少步例如dist[2] 5表示 A 至少需要 5 回合才能到达房间 2。---## 3. 构造 B 的循环轨迹如果 B[1,2,3]那么完整循环为1 - 2 - 3 - 2 - 1因此周期数组[1,2,3,2]第 t 回合 B 所在位置cycle[t % cycle.length]---## 4. 判断相遇第 t 回合如果dist[B当前位置] t说明A 最多 t 步已经可以到达 B 所在房间。因此第一个满足条件的 t 就是答案。---# Go代码package main import fmt func bfs(start int, graph [][]int) []int { n : len(graph) dist : make([]int, n) for i : 0; i n; i { dist[i] -1 } queue : []int{start} dist[start] 0 for head : 0; head len(queue); head { cur : queue[head] for _, next : range graph[cur] { if dist[next] -1 { dist[next] dist[cur] 1 queue append(queue, next) } } } return dist } func buildCycle(path []int) []int { if len(path) 1 { return path } cycle : []int{} for _, v : range path { cycle append(cycle, v) } for i : len(path)-2; i 1; i-- { cycle append(cycle, path[i]) } return cycle } func solve( startA int, graph [][]int, pathB []int, ) int { dist : bfs(startA, graph) cycle : buildCycle(pathB) for t : 0; ; t { room : cycle[t%len(cycle)] if dist[room] ! -1 dist[room] t { return t } if t 100000 { break } } return -1 }---# 复杂度分析设- 房间数量为 N- 通道数量为 MBFSO(N M)空间O(N M)---# 总结这道题的核心思想不要直接模拟 A 的移动。因为 A 可以自由选择路线。应该1. BFS 预处理 A 到所有房间的最短距离2. 周期模拟 B 的位置3. 判断A最短距离 当前时间即可。本质图最短路 周期状态模拟