P1135 奇怪的电梯
题目背景
感谢 @yummy 提供的一些数据。
题目描述
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 \(i\) 层楼（\(1 \le i \le N\)）上有一个数字 \(K_i\)（\(0 \le K_i \le N\)）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：\(3, 3, 1, 2, 5\) 代表了 \(K_i\)（\(K_1=3\)，\(K_2=3\)，……），从 \(1\) 楼开始。在 \(1\) 楼，按“上”可以到 \(4\) 楼，按“下”是不起作用的，因为没有 \(-2\) 楼。那么，从 \(A\) 楼到 \(B\) 楼至少要按几次按钮呢？
输入格式
共二行。
第一行为三个用空格隔开的正整数，表示 \(N, A, B\)（\(1 \le N \le 200\)，\(1 \le A, B \le N\)）。
第二行为 \(N\) 个用空格隔开的非负整数，表示 \(K_i\)。
输出格式
一行，即最少按键次数，若无法到达，则输出 -1。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
对于 \(100 \%\) 的数据，\(1 \le N \le 200\)，\(1 \le A, B \le N\)，\(0 \le K_i \le N\)。
本题共 \(16\) 个测试点，前 \(15\) 个每个测试点 \(6\) 分，最后一个测试点 \(10\) 分。
Tip
📌 题目分析
给定数据：
要求计算从起点 \(A\) 楼到终点 \(B\) 楼的最少按键次数。如果无法到达，输出 -1。
👉 本质：
👉 类型：
🧠 解题思路
1️⃣ 为什么求“最少次数”首选 BFS？
这道题是经典的“隐式图”寻路问题。每一层楼就是一个节点，按“上”或“下”就是从当前节点连出两条边，且每按一次按钮的代价（边权）都是 \(1\)。 在所有边权均为 \(1\) 的情况下去寻找最短路径（最少按键次数），广度优先搜索 (BFS) 是唯一的神。它像水波一样一层一层向外扩展，第一次蔓延到终点时，所经历的层数绝对就是最短的。如果用 DFS 去找，不仅极易陷入死循环，还需要穷举所有路径来比对最小值，必将导致超时。
2️⃣ 状态的存储与边界判断
- 状态队列：我们需要一个队列
queue来存储接下来要探索的楼层。 - 访问标记兼步数记录：我们可以开一个数组
dist[205]，统一初始化为-1。当探索到新楼层时，dist[新楼层] = dist[当前楼层] + 1。这样dist既记录了走到这里的最小步数，又充当了vis访问标记（只要不是-1就说明来过，防止在两层楼之间无限上下弹跳）。 - 合法性检查：每次计算出新楼层
nx后，必须检查它是否在 \([1, N]\) 的范围内。
3️⃣ 时间复杂度
借助 BFS，每个楼层最多被加入队列一次，弹出一次。 每个楼层只有“上”和“下”两个扩展方向。
\(N\) 最大只有 200，运算次数在几百次级别，耗时完全可以忽略不计（\(0\) 毫秒秒杀）。
💻 C++代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
// I/O 优化
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, a, b;
cin >> n >> a >> b;
vector<int> k(n + 1);
for (int i = 1; i <= n; i++) {
cin >> k[i];
}
// dist 数组初始化为 -1，兼具“访问标记”和“步数记录”的双重功能
vector<int> dist(n + 1, -1);
queue<int> q;
// 1. 起点初始化
dist[a] = 0;
q.push(a);
// 2. 广度优先搜索
while (!q.empty()) {
int curr = q.front();
q.pop();
// 优化剪枝：一旦弹出的楼层是终点，直接退出搜索
if (curr == b) {
break;
}
// 尝试向上走
int up_floor = curr + k[curr];
if (up_floor <= n && dist[up_floor] == -1) {
dist[up_floor] = dist[curr] + 1;
q.push(up_floor);
}
// 尝试向下走
int down_floor = curr - k[curr];
if (down_floor >= 1 && dist[down_floor] == -1) {
dist[down_floor] = dist[curr] + 1;
q.push(down_floor);
}
}
// 3. 输出结果（如果没走到，dist[b] 依然是最初始的 -1，完美契合题意）
cout << dist[b] << "\n";
return 0;
}
⚠️ 易错点
❌ 1. 忘记标记已访问状态导致死循环
如果在队列 push 时不检查 dist[新楼层] == -1（或使用独立的 vis 数组），当你在 3 楼按下到了 1 楼，在 1 楼按上又回到了 3 楼。队列会被无休止地塞入重复的楼层，瞬间导致内存超限 (MLE) 和时间超限 (TLE)。
❌ 2. 起点与终点相同的情况
如果输入是 5 3 3（直接就在终点楼层），正确的按键次数应该是 \(0\)。
如果你是先将周围节点入队，判断到达终点时步数加一才判定结束，可能会算出错误的值。我们代码中 dist[a] = 0 且在 q.pop() 之后立刻检查 curr == b，就能完美地处理起点与终点重合的边缘情况。
❌ 3. 数组越界
这题的楼层是严格从 \(1\) 开始到 \(N\) 结束的。往上走时必须判断 <= n，往下走时必须判断 >= 1。如果不加限制地直接操作 dist 数组，必定会引发段错误（RE）。
🚀 一句话总结
🔥 补充：硬核知识点
双向广度优先搜索 (Bidirectional BFS)
虽然这道题 \(N \le 200\)，单向 BFS 足以秒杀。但如果 \(N\) 扩大到 \(10^7\)（比如魔方还原状态、复杂的迷宫寻路），单向 BFS 的搜索树会呈指数级爆炸，把内存瞬间撑爆。
这时候，高阶选手会祭出 双向 BFS：
既然我们知道了起点 \(A\) 和终点 \(B\)，我们不如让起点和终点同时往中间搜索！
* 建立两个队列，一个是正向探索的 q_forward，一个是反向探索的 q_backward。
* 每次挑元素较少的那一端扩展一层。
* 只要正向的波纹和反向的波纹在某个中间节点相遇（即某个节点在两个方向的 dist 数组中都不是 -1），那么 dist_forward[中间点] + dist_backward[中间点] 就是全局最短路！
降维打击原理：假设单向搜索的扩散分支因子为 \(K\)，深度为 \(D\)，总状态数是 \(O(K^D)\)。如果双向齐发，它们在中间 \(D/2\) 处相遇，搜索状态数会骤降至 \(O(K^{D/2} + K^{D/2})\)。这种优化在庞大的状态空间题中，性能提升可达上万倍。