1. 题目内容与核心思路1.1 题意重述一座“不太智能”的电梯先花三十秒把原题说清楚。假设一栋楼有N层你在第A层想去第B层。每层电梯门口都只有一个按钮按钮上写着一个数字Ki这个数字不是楼层号而是“从第i层出发电梯只能上下一趟固定的距离”按一下按钮电梯会上升Ki层或者下降Ki层。注意这里没有“按几层”的选项你面对的就是单键电梯——按一次要么加Ki要么减Ki目标楼层必须在1到N的范围内否则这次移动无效。输入会给你N、A、B以及每层对应的Ki。你要计算从A到B最少需要按多少次按钮如果根本到不了输出-1。数据范围我记得很清楚N不超过200Ki的值也不会特别夸张但就是这种量级题干读起来也足够让人一开始绕进去。这个题的经典程度在于它几乎是所有算法入门选手接触“最短路/搜索”问题时一定会撞上的题目。表面上看是一个电梯模拟实际上是一个赤裸裸的图论模型每个楼层是图上的一个点能按一次按钮到达的楼层就是一条边边的权重统一为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标记是最省心的做法。还有一种写法是直接用queuepairint,intpair里存楼层号和当前步数省去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)); queueint 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层Ki1往上到第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)虽然N200也跑得完但思考方式完全偏了。做图论题一定要建立“点—边”的抽象不要被题面里的物理场景困住。3. 两种主流解法的选型对比3.1 朴素BFS与最短路算法的对照这个题除了BFS还有几种常见解法我整理成一张对比表方便你根据自己的水平选择解法方向思路核心时间复杂度实现难度适用场景朴素BFS逐层扩展第一次到达即最优O(N)低边权全部为1Dijkstra优先队列维护当前最短路O(N log N)中边权不全为1SPFA队列优化Bellman-Ford理论O(N·M)中高可能有负权边Floyd全源最短路三重循环O(N^3)低N很小且需要所有起点记忆化DFS递归剪枝查表视剪枝而定中适合理解搜索本质这个题边权全是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数组也就开N1个位置0号元素没用。如果你的Ki数组从0开始存那么“第i层”对应的K值就变成了k[i-1]非常容易错位。更隐蔽的问题是越界访问。比如cur1向下走后nxt1-k[1]这时候如果k[1]5nxt-4。你访问step[-4]就直接访问了数组越界内存轻则得到垃圾值重则运行时错误。所以判断顺序必须是先判断范围再访问数组不能反过来。我自己的习惯是先把向上向下的判断写成两个独立的if块每个块内第一行判断范围第二行判断vis。这样逻辑清晰一屏能看完不容易漏。4.2 剪枝无效的根因有的同学看别人的题解里写“如果step[cur]1已经大于当前最优解就剪枝”于是照抄结果发现没用。为什么因为这个剪枝在BFS里本来就是多此一举。BFS按层扩展第一次到达某个点就是最短距离不存在“到达时步数比之前大”的情况。如果你用DFS这个剪枝确实能大幅提速但BFS天然不需要它。换句话说剪枝本身没错但它解决的问题在BFS里已经被队列顺序解决了。如果你想剪枝唯一有点用的是如果上下两个方向中有任何一个超出了楼层范围那就只走合法的那一侧甚至两侧都不合法就直接跳过。但这些其实是边界条件不能叫剪枝。4.3 样例手推与边界用例我用一组小数据手推一遍帮助你把流程走顺。假设N5A1B5每层Ki分别是k[1]3, k[2]3, k[3]1, k[4]2, k[5]1。BFS流程队列刚开始是[1]step[1]0。弹出1向上走134在范围内且未访问step[4]1入队。向下走1-3-2越界忽略。队列变成[4]。弹出4向上走426越界向下走4-22step[2]2入队。队列变成[2]。弹出2向上走235正好是Bstep[5]3输出3。然后结束。手动演算一下这个三条路径的答案对不对从1到4一步4到2一步2到5一步总步数3。确实最短。如果直接用DFS你可能会从1-4-2-1-4陷入无限循环必须依靠vis避免回头。还有一个边界用例值得测试AB的情况直接输出0。如果N1AB1答案还是0。如果N1且A不等于B但实际上A和B必须都在1到N范围内所以这种情况不可能出现不需要处理。另外Ki可以等于0吗题目里其实可以存在Ki0。如果某层Ki0那么坐电梯按一下按钮往上往下都还是当前楼层等于原地不动。处理这种楼层时方向判断会变成cur 0 cur正好等于自己而step[cur]已经不是-1了所以不会被重复加入队列。但特殊数据里可能出现起点不是终点却要经过一个Ki0的楼层这种情况由于原地踏步不能产生任何新状态BFS自然跳过它不会死循环。我实测过Ki0不会造成问题但如果你特判一下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也能做但没必要”的时候你就真正掌握了这道题的精髓。