当前位置：首页 > news >正文

房间追踪相遇问题（BFS + 周期模拟）

news 2026/7/11 17:40:07

# 机考复盘：

> 题意根据考场回忆整理，可能与原题存在细节差异。

## 题目描述

有一个地图，由 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 的移动。