单键电梯问题：用BFS求最少按键次数的最短路解法

1. 题目内容与核心思路

1.1 题意重述：一座“不太智能”的电梯

先花三十秒把原题说清楚。假设一栋楼有N层，你在第A层，想去第B层。每层电梯门口都只有一个按钮，按钮上写着一个数字Ki，这个数字不是楼层号，而是“从第i层出发，电梯只能上下一趟固定的距离”：按一下按钮，电梯会上升Ki层，或者下降Ki层。注意这里没有“按几层”的选项，你面对的就是单键电梯——按一次要么加Ki，要么减Ki，目标楼层必须在1到N的范围内，否则这次移动无效。

输入会给你N、A、B，以及每层对应的Ki。你要计算从A到B最少需要按多少次按钮，如果根本到不了，输出-1。数据范围我记得很清楚，N不超过200，Ki的值也不会特别夸张，但就是这种量级，题干读起来也足够让人一开始绕进去。

这个题的经典程度在于，它几乎是所有算法入门选手接触“最短路/搜索”问题时一定会撞上的题目。表面上看是一个电梯模拟，实际上是一个赤裸裸的图论模型：每个楼层是图上的一个点，能按一次按钮到达的楼层就是一条边，边的权重统一为1（按一次计一步）。于是问题变成了：从点A出发到点B的最少步数是多少。

1.2 第一步思考：为什么它是一道BFS题

很多人第一反应是“用DFS不行吗？”我当初也是这么想的，然后排着队踩坑。

DFS当然可以走到B，但它的问题是：你没法保证第一次搜到B的时候走的就是最短路径。因为DFS会沿着一条路一直深入，如果这条路绕远了，你同样能到B，但步数可能比别的路多很多。除非你用一个全局变量记录当前最优解，并且一旦当前深度已经超过了最优解就剪枝——但在这个数据范围下，剪枝效果并不稳定，最坏情况下还是可能把一个简单问题跑成指数级。

BFS就不一样了。BFS的特性是逐层扩展：先把起点能一步到达的所有点标记为“步数为1”，再把它们能一步到达且没被访问过的点标记为“步数为2”，以此类推。因为所有边的权重都是1，第一次从队列里弹出B的时候，记录下来的步数一定是最小的。

这个结论背后的直觉很简单：BFS的队列天然保证“先入队的点步数一定小于等于后入队的点”。你按层推进，不会出现某个步数更大的节点提前跑到B的情况。这也是为什么只要所有边权相同，BFS就是最短路问题的首选。

1.3 数据范围蕴含的信号

N≤200这个范围其实泄露了很多信息。

200个点，每个点最多引出两条边（向上Ki、向下Ki），所以整个图的规模非常小，BFS一遍的时间复杂度是O(N)，理论上连优化都不用做。这时候如果你去写一个Dijkstra，也能过，但没必要——属于杀鸡用牛刀，还容易写错堆优化。更有意思的是，这个范围下用Floyd跑一遍全源最短路也是秒过的，因为N的三次方是八百万，对现代CPU来说就是一瞬间的事。

我当时做题时的判断标准是这样的：看到N≤200，先想BFS；看到N≤1000，想BFS或简单Dijkstra；看到N到了10^5，才需要考虑堆优化或线段树这类高级工具。做题先看数据范围，这个习惯能帮你避开一半以上的无效优化。

2. 标准BFS解法拆解

2.1 状态设计与队列规划

先搭一个最简单的状态模型。每一层楼只有一个值得记录的属性：从A出发到达该层最少需要按几次按钮。用数组step[i]来存，初始化为一个很大的数（比如-1表示还没访问过）。

队列里放的是“当前到达的楼层编号”。从A入队开始，每次从队首取出一个楼层cur，检查两个方向：

• 向上：nxt = cur + K[cur]
• 向下：nxt = cur - K[cur]

重点是转移前的合法性判断。nxt必须在[1, N]范围内，并且step[nxt]必须还是-1，表示这个楼层第一次被访问。一旦满足条件，就更新step[nxt] = step[cur] + 1，然后把这个楼层push进队列。

为什么要求“第一次访问”而不是“允许重复入队”？因为BFS的核心保证就是“第一次到达某点的路径已经是最短路径”。如果允许重复入队，虽然最终结果可能还是对的，但队列里会出现大量无效节点，空间和时间都浪费，而且你还要额外处理“节点被多次更新”的逻辑。这里统一用vis标记是最省心的做法。

还有一种写法是直接用queue<pair<int,int>>，pair里存楼层号和当前步数，省去step数组的第二重索引。两种都可以，但我在比赛环境里更喜欢单独开step数组，因为后面查错方便——调试的时候直接打印step数组，每个楼层的最优步数一目了然。

2.2 核心代码实现

直接用C++写一个最标准的版本：

#include <bits/stdc++.h> using namespace std; const int MAXN = 205; int k[MAXN], step[MAXN]; int main() { int n, a, b; cin >> n >> a >> b; for (int i = 1; i <= n; i++) { cin >> k[i]; } if (a == b) { cout << 0 << endl; return 0; } memset(step, -1, sizeof(step)); queue<int> q; step[a] = 0; q.push(a); while (!q.empty()) { int cur = q.front(); q.pop(); int up = cur + k[cur]; if (up >= 1 && up <= n && step[up] == -1) { step[up] = step[cur] + 1; if (up == b) { cout << step[up] << endl; return 0; } q.push(up); } int down = cur - k[cur]; if (down >= 1 && down <= n && step[down] == -1) { step[down] = step[cur] + 1; if (down == b) { cout << step[down] << endl; return 0; } q.push(down); } } cout << -1 << endl; return 0; }

这段代码有几个值得说一说的细节。

第一个小细节是a == b的特判。如果起点就是终点，答案显然是0，不需要做任何BFS。这个特判有些人会忽略，但它能省掉一次不必要的搜索，对代码逻辑也更清晰。

第二个细节是判断step[up] == -1和step[down] == -1。这是BFS去重的核心。比如你在第2层，Ki=1，往上到第3层；等你在第3层的时候，往下也是到第2层。如果没有vis标记，第2层会被反复入队，造成死循环式的队列膨胀，虽然最终会因为队列清空而停止，但慢得离谱。

第三个细节是提前判断up == b。其实这不是必须的，你完全可以等到从队列里弹出b的时候再输出step[b]。但提前判断的好处是能省掉一些不必要的入队操作，也能让逻辑更直观。我测试过这两种写法在这个数据范围下性能没有区别，纯粹是编码习惯问题。

2.3 复杂度为什么是O(N)

来分析一下。每个楼层最多被入队一次，因为vis标记的存在保证了这一点。每个楼层出队后，最多扩展两个方向（向上和向下），所以总操作次数大约是2N次队列操作加上N次判断。整体复杂度O(N)，空间复杂度同样是O(N)。

很多人会误以为这是O(N^2)，因为他们把“每个楼层扩展两个方向”想成“每个楼层都要尝试所有楼层”。这是理解偏差。在这个题里，每个楼层只有一个固定的Ki，所以从它出发只有两条固定的边，不存在遍历其他所有楼层的操作。正因为边数等于点数级别的量级，BFS才能在线性时间内完成。

我之前带过一个同学，他一开始写成：

for (int i = 1; i <= n; i++) { // 尝试从cur跳到所有楼层 }

这当然也能做，但复杂度直接变成O(N^2)，虽然N=200也跑得完，但思考方式完全偏了。做图论题一定要建立“点—边”的抽象，不要被题面里的物理场景困住。

3. 两种主流解法的选型对比

3.1 朴素BFS与最短路算法的对照

这个题除了BFS，还有几种常见解法，我整理成一张对比表，方便你根据自己的水平选择：

这个题边权全是1，用BFS是理论上最优的选择。但如果你没学过BFS，直接用Dijkstra也能过，因为N只有200，堆优化Dijkstra跑一遍也就是几十毫秒的事。SPFA在这个题上属于过度设计，而且负权边在这个题里不存在，没必要用。

我个人的建议是：BFS不过关的，直接把这道题当成练BFS的模板题。等BFS刷熟以后，再回头用Dijkstra或者Floyd写一遍，作为复习最短路算法的练习。同一个题用不同算法写三遍，对理解算法之间的区别帮助很大。

3.2 什么时候我会改用Dijkstra或DP

说句实话，如果题目稍微改一下，电梯不仅能上下Ki层，还能额外选择“停留不前”或者“某个楼层可以花2次按钮跳两层”——边权就不全是1了，BFS就不能保证最优了。到那时候，Dijkstra或SPFA就变成必须的。

另一个值得说的思路是DP。某些类似于“最少步数到终点”的问题可以转成动态规划，尤其是当图的结构具有明确方向性时。但电梯向上和向下都能走，存在环路，DP会有循环依赖，处理起来麻烦，所以我不太推荐在这个题上用DP。它天然是一个图模型，走搜索/最短路才顺。

遇到这个题的时候，我还想过“双向BFS”。原理是从起点和终点同时做BFS，两边相遇时路径总长就是答案。这道题数据范围实在太小，双向BFS的优势体现不出来。但如果N扩大到10^5甚至10^6，且每条边都是无向的，双向BFS能把搜索空间从N减少到大约2√N量级，这在大数据范围下是妥妥的优化。我建议初学者先把单向BFS熟练了，再研究双向，不然容易一头雾水。

4. 常见问题与避坑实录

4.1 数组越界和下标错位

我见过太多人在这个题上栽在数组下标上。这个题楼层编号从1到N，数组也就开N+1个位置，0号元素没用。如果你的Ki数组从0开始存，那么“第i层”对应的K值就变成了k[i-1]，非常容易错位。

更隐蔽的问题是越界访问。比如cur=1，向下走后nxt=1-k[1]，这时候如果k[1]=5，nxt=-4。你访问step[-4]就直接访问了数组越界内存，轻则得到垃圾值，重则运行时错误。所以判断顺序必须是先判断范围再访问数组，不能反过来。

我自己的习惯是：先把向上向下的判断写成两个独立的if块，每个块内第一行判断范围，第二行判断vis。这样逻辑清晰，一屏能看完，不容易漏。

4.2 剪枝无效的根因

有的同学看别人的题解里写“如果step[cur]+1已经大于当前最优解就剪枝”，于是照抄，结果发现没用。为什么？

因为这个剪枝在BFS里本来就是多此一举。BFS按层扩展，第一次到达某个点就是最短距离，不存在“到达时步数比之前大”的情况。如果你用DFS，这个剪枝确实能大幅提速，但BFS天然不需要它。换句话说，剪枝本身没错，但它解决的问题在BFS里已经被队列顺序解决了。

如果你想剪枝，唯一有点用的是：如果上下两个方向中有任何一个超出了楼层范围，那就只走合法的那一侧，甚至两侧都不合法就直接跳过。但这些其实是边界条件，不能叫剪枝。

4.3 样例手推与边界用例

我用一组小数据手推一遍，帮助你把流程走顺。

假设N=5，A=1，B=5，每层Ki分别是：k[1]=3, k[2]=3, k[3]=1, k[4]=2, k[5]=1。

BFS流程：

• 队列刚开始是[1]，step[1]=0。
• 弹出1，向上走1+3=4，在范围内且未访问，step[4]=1，入队。向下走1-3=-2，越界，忽略。队列变成[4]。
• 弹出4，向上走4+2=6越界，向下走4-2=2，step[2]=2，入队。队列变成[2]。
• 弹出2，向上走2+3=5，正好是B，step[5]=3，输出3。然后结束。

手动演算一下，这个三条路径的答案对不对？从1到4一步，4到2一步，2到5一步，总步数3。确实最短。如果直接用DFS，你可能会从1->4->2->1->4陷入无限循环，必须依靠vis避免回头。

还有一个边界用例值得测试：A=B的情况，直接输出0。如果N=1，A=B=1，答案还是0。如果N=1且A不等于B（但实际上A和B必须都在1到N范围内，所以这种情况不可能出现），不需要处理。

另外，Ki可以等于0吗？题目里其实可以存在Ki=0。如果某层Ki=0，那么坐电梯按一下按钮，往上往下都还是当前楼层，等于原地不动。处理这种楼层时，方向判断会变成cur + 0 = cur，正好等于自己，而step[cur]已经不是-1了，所以不会被重复加入队列。但特殊数据里可能出现起点不是终点却要经过一个Ki=0的楼层这种情况，由于原地踏步不能产生任何新状态，BFS自然跳过它，不会死循环。我实测过，Ki=0不会造成问题，但如果你特判一下k[cur] == 0，提前跳过这次扩展，心里更踏实。

5. 从一道题延伸到一类题

5.1 “电梯模型”的通用化

这道题实际上是一个典型的“图上最短路”模型，剥掉电梯的外壳，换成“跳格子”“走迷宫”“状态转换”都一样成立。我后来遇到过不少题，本质上就是这道题的变体：

• 数字转换问题：每次操作可以把当前数乘以某个数或者减去某个数，问几步变成目标数。图上的点就是每个数字，边就是操作。
• 滚动数组问题：数组长度固定，每次只能移动某个固定步长，本质也是BFS。
• 推箱子的一些简化版本：每个状态是一个“位置二元组”，转移有限，求最短步数。

遇到这类题时，通用的思考顺序是四步：定义状态、画转移边、选择搜索算法、优化判断条件。把这四步练成本能，比背一百道题的代码都有用。

5.2 一个常见误区：BFS与DFS的选择逻辑

我经常被问：“DFS加vis也一样能求最短路，为什么一定要学BFS？”这是个好问题，答案是：DFS加vis能找到一条路径，但无法保证是最短路径。

你可以让DFS记录所有到达终点的路径再比较，但那样复杂度是路径数量级别的，指数爆炸。而BFS由于一层层地推进，天然保证第一次到终点就是最优解。这也是为什么“最短路径”类的搜索题，标准答案几乎都是BFS。

反过来说，有些题用DFS反而更方便。比如“是否存在一条路径满足某个约束”“枚举所有可能方案”“回溯法解决排列问题”，这些都是DFS的舒适区。两者不是谁取代谁的关系，而是各自解决不同的搜索需求。把这两个搜索框架都练到肌肉记忆，算法才算入了门。

5.3 我的实操沉淀

最后分享一个我做这类题的习惯供你参考：拿到题目后，先在草稿纸上画出状态转移图，哪怕只有三五个点，也要画出来。画图的过程会逼你把题意翻译成“点—边—权重”的语言，这一步做了，思路基本就清晰了。然后再写代码，你会发现代码只是把图画翻译成编程语言而已。

这个题我写过的版本不下五种，从最笨的DFS到BFS、双向BFS、Dijkstra、Floyd，每一种跑出来的结果都一样，但每种写法的思考方式差异很大。对一个入门选手，我不建议一开始就追求“最优化算法”，而是先把一种解法写熟练，再横向拓展到其他解法。等你能对着一个题自然说出“这个题用BFS是因为边权为1，用Dijkstra也能做但没必要”的时候，你就真正掌握了这道题的精髓。