房间追踪相遇问题（BFS + 周期模拟）
# 机考复盘：
> 题意根据考场回忆整理，可能与原题存在细节差异。
## 题目描述
有一个地图，由 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 1
1 2
2 3
3 4
```
图结构：
```
0 - 1 - 2 - 3 - 4
```
A：
```
startA = 0
```
B：
```
[4,3,2]
```
B 的运动轨迹：
```
4 -> 3 -> 2 -> 3 -> 4 -> 3 -> 2 ...
```
### 分析
A 到各房间的最短距离：
```
dist[0] = 0
dist[1] = 1
dist[2] = 2
dist[3] = 3
dist[4] = 4
```
模拟 B：
| 时间 | B位置 | A是否可到达 |
|----|----|----|
|0|4|需要4步，不行|
|1|3|需要3步，不行|
|2|2|需要2步，可以|
答案：
```
2
```
---
# 解题思路
## 1. 建图
房间和通道组成一个无权图。
使用邻接表：
```
graph[i] = 与房间 i 相连的房间
```
---
## 2. BFS 求 A 到所有房间的最短距离
因为 A 每回合只能移动一条边，所以：
使用 BFS：
```
dist[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
- 通道数量为 M
BFS：
```
O(N + M)
```
空间：
```
O(N + M)
```
---
# 总结
这道题的核心思想：
不要直接模拟 A 的移动。
因为 A 可以自由选择路线。
应该：
1. BFS 预处理 A 到所有房间的最短距离；
2. 周期模拟 B 的位置；
3. 判断：
```
A最短距离 <= 当前时间
```
即可。
本质：
```
图最短路 + 周期状态模拟
```