洛谷P1135奇怪电梯：从图论建模到BFS/DFS剪枝与双向BFS全解析-北京尧图网络

第一次读到P1135的时候我盯着题目看了半天不太明白这个“奇怪的电梯”到底想干什么。后来想明白了它根本不关心你是不是按错了楼层按钮。这台电梯的逻辑是你在第 i 层它只会往上走 k[i] 层或者往下走 k[i] 层没有别的选项。换句话说你按的楼层只是一个目标真正决定你能不能到达的是每一层上的那个固定数字。这道题在洛谷上的题号是 P1135属于搜索算法的入门经典。对新手来说它最大的价值不是“会做”而是能让你第一次体会到把生活里一个看着很奇怪的规则翻译成图论里的节点和边然后用 BFS 或 DFS 去解决。这篇文章我会从建模开始讲给出 BFS、DFS 剪枝的完整代码再聊聊双向 BFS 的坑和边界细节。无论你是刚学搜索还是已经会写模板但总在细节上卡住都能找到点东西。1. 奇怪的电梯到底在考什么把生活问题翻译成图论1.1 题面背后其实是一个图先回忆一下题目给的条件。有一栋 N 层的楼每层楼对应一个数字 k[i]。你从 A 层出发如果当前在第 i 层那么电梯只能去 i k[i] 层或者 i - k[i] 层。注意前提是不越界楼层必须落在 1 到 N 的范围内。问你从 A 层到 B 层最少需要按几次按钮如果到不了就输出 -1。我第一次做这题时潜意识里把 k[i] 当成“电梯的固定行程”总觉得应该从按钮入手。但一旦你画出状态图事情就变得很清楚每一层楼是一个节点从节点 i 出发最多有两条边分别指向 i k[i] 和 i - k[i]。按一次按钮就是从当前节点走到相邻节点代价为 1。所以这道题的本质是在一个最多 N 个节点、每个节点出度不超过 2 的图上求从 A 到 B 的最短路径长度。1.2 一次小规模手算感受状态爆炸的方向看一个具体的例子。假设 N6k[1]2k[3]3A1B6。从 1 层出发唯一能去的是 3 层因为 1-2 -1 越界。这一步按了第 1 次按钮到达 3 层。在 3 层k[3]3可以到 6 层或 0 层0 层越界所以只能去 6 层。这一步按了第 2 次按钮到达 6 层。答案就是 2。这个例子看着简单但如果你把 N 放大到 200把状态展开画一画会发现搜索树并不是一条单链。尤其当 k[i] 比较小时你可能会在几个楼层之间来回折腾比如从 5 层跳到 3 层又从 3 层跳到 5 层。这种“来回跳”的情况正是搜索题最容易出现死循环的地方后面我会专门说。1.3 为什么“按几次”能被当作最短路径这个转换的关键在于“按一次按钮”的代价是统一的 1。路径长度按钮次数所以从 A 到 B 的最少按钮次数就是无权图上的最短路径。如果每次按键的代价不一样比如不同楼层按钮的磨损程度不同那就得用 Dijkstra。如果允许“原地等待一次”作为选项那模型又变成 01BFS。这就是为什么我建议新手做这道题时不要急着写代码先在纸上画一画“节点-边”结构因为这决定了你后面选哪种算法。一句话总结洛谷 P1135 考的不是电梯而是你有没有把陌生规则转成熟悉模型的能力。2. BFS解法为什么“第一次碰到就是最优解”是核心2.1 边权为 1 的图BFS 就是天然最短路径算法BFS广度优先搜索的思路是从起点出发一层一层往外扩展。第 0 层是起点第 1 层是所有按一次按钮能到的楼层第 2 层是从第 1 层再按一次能到的楼层以此类推。因为它严格按“扩展轮数”递增的顺序访问节点所以当一个节点第一次被访问到时它所在的层次就是从起点到它的最短按钮次数。这是 BFS 最漂亮的性质也是它适合这道题的根本原因。这里值得多说一句很多新手会混淆“第一次访问”和“第一次入队”。在 BFS 里我用一个 visited 数组或 dist 数组标记楼层是否已经被访问过。如果某个楼层已经在队列里或者已经出队过那后续再遇到它直接跳过。因为后续到达它的路径长度不会比第一次更短。2.2 状态设计与队列流程状态只需要两个信息当前楼层编号以及到达这个楼层已经按了几次按钮。但实际写代码时我会用一个 dist 数组来存“从起点到该楼层的最短步数”初始化为 -1 表示还没访问过这样队列里就只需要存楼层编号。核心流程初始化 dist[A] 0把 A 入队。只要队列不空取出队首楼层 cur。如果 cur 等于目标 B直接返回 dist[cur]。计算两个邻居up cur k[cur]down cur - k[cur]。对于每个邻居 nxt如果它在 1 到 N 范围内并且 dist[nxt] 仍然为 -1就执行 dist[nxt] dist[cur] 1并入队。如果队列空了还没找到 B说明不可达返回 -1。2.3 C 参考实现#include bits/stdc.h using namespace std; const int MAXN 205; int n, A, B; int k[MAXN]; int dist[MAXN]; int bfs() { memset(dist, -1, sizeof(dist)); queueint q; q.push(A); dist[A] 0; while (!q.empty()) { int cur q.front(); q.pop(); if (cur B) { return dist[cur]; } int up cur k[cur]; int down cur - k[cur]; if (up n dist[up] -1) { dist[up] dist[cur] 1; q.push(up); } if (down 1 dist[down] -1) { dist[down] dist[cur] 1; q.push(down); } } return -1; } int main() { cin n A B; for (int i 1; i n; i) { cin k[i]; } cout bfs() endl; return 0; }这份代码能直接过洛谷 P1135。我没有用数组模拟队列而是直接用 STL 的 queue因为 N 最大才 200队列开销不值一提。2.4 时间复杂度与“为什么不直接用Dijkstra”BFS 的时间复杂度是 O(N)空间复杂度 O(N)。因为每个楼层最多入队一次出队一次而每次出队只检查两个邻居总操作次数是线性的。有人可能会问既然是最短路径为什么不用 Dijkstra原因很简单Dijkstra 是为带权图设计的它需要优先队列来维护当前最小代价复杂度是 O((NE)logN)。在本题这种边权全部为 1 的图上用 Dijkstra 属于杀鸡用牛刀而且写起来更绕。BFS 用普通队列就够了先入先出的顺序天然等价于“按层扩展”。我记得自己刚学搜索的时候总觉得 Dijkstra 更“高级”什么题都想往上套。后来做多了才发现选算法不是选最复杂的而是选最匹配问题性质的。边权为 1就用 BFS没有第二种更好的选择。3. DFS剪枝另一条能过但需要小心的路3.1 DFS 最容易写但也最容易超时BFS 是这题的标准解法但很多初学者一开始想到的其实是 DFS。为什么因为 DFS 的递归写法非常符合直觉从当前楼层出发先往一个方向走到底再回来走另一个方向。代码量看起来比 BFS 还少。但直接这样写结果往往很惨。一个没有剪枝的 DFS 会把你上下楼层之间的循环路径全部搜一遍。比如你在第 5 层k[5]1向上到 66 层如果 k[6]1又能回到 5。DFS 会在这种来回路径上不断递归直到栈溢出或超时。所以用 DFS 做这道题不是在“搜索”而是在“有策略地搜索”。核心就是剪枝。3.2 剪枝的四个要点第一个剪枝也是最关键的记忆化。维护一个数组 best[cur]记录当前已知到达 cur 层的最小步数。如果某次搜索到达 cur 层时步数已经大于等于 best[cur]直接返回。这相当于把一棵指数级的搜索树砍成每个节点最多被有效访问一次。第二个剪枝是答案上界。维护一个全局变量 ans初始化为一个很大的数。只要当前步数已经大于等于 ans就不再往下搜。因为就算继续走到目标步数也不会比 ans 更优。第三个剪枝是方向顺序。搜索时先走更有可能接近目标的方向。这不算严格的复杂度优化但在很多数据上能让你更早更新 ans从而让第二个剪枝发挥更大作用。第四个剪枝是边界判断。每次递归前先判断越界越界分支根本不该进入递归。3.3 C 参考实现#include bits/stdc.h using namespace std; const int MAXN 205; const int INF 1e9; int n, A, B; int k[MAXN]; int best[MAXN]; int ans INF; void dfs(int cur, int cnt) { if (cur B) { ans min(ans, cnt); return; } if (cnt ans || cnt best[cur]) { return; } best[cur] cnt; int up cur k[cur]; int down cur - k[cur]; // 优先搜索更靠近目标的方向 if (up n) { dfs(up, cnt 1); } if (down 1) { dfs(down, cnt 1); } } int main() { cin n A B; for (int i 1; i n; i) { cin k[i]; } fill(best, best n 1, INF); dfs(A, 0); cout (ans INF ? -1 : ans) endl; return 0; }这里有个细节我在更新 best[cur] 时是“如果当前步数已经不小于 best[cur] 就返回”否则更新。也就是说每个楼层只会被更优路径访问一次最坏情况下每个节点进入一次递归配合剪枝后复杂度接近 O(N)。3.4 什么时候该用 DFS而不是 BFS既然 BFS 又稳又简单为什么还要讨论 DFS因为在面试或笔试题里有些搜索问题并不要求“最短”只要求“是否存在一条路径”这时候 DFS 占用的内存更少。还有一类题目搜索空间是矩阵或树形结构递归写法比 BFS 的队列写法更自然。但在 P1135 这种明确要求最短按钮次数的题目里BFS 是首选。如果你的目标是练 DFS那可以用这题当剪枝练习题但别把它当成常规手段。我见过不少同学在 DFS 里只加了“是否访问过”的 bool 数组结果 WA。原因是相同的楼层完全可能通过不同的步数到达单纯标记“来过”会把一条更短的路给挡掉。必须像上面那样用 best[cur] 存最小步数而不是用布尔值。4. 数据范围变大怎么办双向BFS与它的一个经典陷阱4.1 升级 BFS 的自然想法如果 N 从 200 变成 10 万甚至更大普通 BFS 依然是 O(N)理论上也能跑。但有一种常见场景会让 BFS 变慢图的分支因子很大。比如这个节点不是只连两个邻居而是连几百个邻居那每一层的节点数量会指数膨胀。这时候有一个思路叫“双向 BFS”从起点和终点同时开始扩展让两边在中间相遇。但 P1135 每个节点的出度最多是 2BFS 的扩展规模天然很小双向 BFS 在这里并不会带来质变。我之所以专门写这一节是因为很多人在学习“双向 BFS”这个概念时会在类似的题目上踩一个隐蔽的坑。4.2 反向扩展的陷阱有向边不是对称的注意这道题里的边是“有向”的。我说的不是电梯能上能下这个表面对称而是如果从 i 层能到 i k[i] 层不代表从 i k[i] 层能回到 i 层。因为从 i k[i] 层出发只能到 i k[i] ± k[i k[i]]这个值不一定等于 i。举个例子。k[2] 5那么从 2 层向上到 7 层。但从 7 层出发只能到 7 k[7] 或者 7 - k[7]除非 k[7] 恰好等于 5否则永远回不到 2。这带来一个非常关键的问题双向 BFS 从终点反向扩展时不能简单地把“u k[u] 和 u - k[u]”当成 u 的前驱。你需要找到所有满足“v k[v] u 或 v - k[v] u”的 v这些 v 才是 u 的前驱。很多新手在写双向 BFS 时把起点和终点的扩展代码写成一模一样最后答案不对还以为是双向 BFS 本身有问题。其实问题出在这这是有向图反向扩展需要遍历前驱节点。4.3 正确的双向 BFS 思路一种简单的处理方式是先预处理一个反图也就是对每一层 v记录它“能走到哪些层”再把这些关系反向建边。这样从终点扩展时直接查反图就能找到当前层的所有前驱。对于 N 比较小的题目反向扩展时可以直接遍历 1 到 N 的所有楼层判断它们是否能一步走到当前节点。N200 时这种 O(N) 的遍历完全能接受。但一旦 N 变大每次都遍历 N 个节点就不划算了所以预处理反图才是通用做法。双向 BFS 的相遇条件是某一层在正向扩展时发现它已经被反向访问过或者反向扩展时发现它已经被正向访问过。此时答案就是正向步数加反向步数。注意在把新节点加入队列前就要检查相遇否则会平白多扩展一层。如果只是想稳稳通过 P1135我建议直接用普通 BFS。把双向 BFS 当成扩展知识来理解即可不要为了炫技而增加代码复杂度。4.4 如果题目条件变化算法怎么升级这节最后我按自己的经验总结一张表方便你以后遇到变体题时对号入座。问题变化适用算法原因每次按键代价不同Dijkstra边权不再是 1需要用优先队列维护最小代价允许原地等待一回合01BFS原地等待看成权值为 0 的自环双向队列维护两种代价图的分支因子很大双向 BFS从两端扩展可以有效减少中间层节点数量只问可不可达DFS / BFS 均可不需要最短路只做连通性判断即可这张表不是让你背下来而是告诉你算法选型跟着问题性质走。P1135 的边权为 1、出度为 2BFS 就是最合适的选择没有之一。5. 网上题解不会细说的边界细节与调试心得5.1 k[i] 为 0原地踏步与死循环这是这道题我见过最多人踩的坑。k[i] 可以是 0也就是说你在某些楼层无论按“上”还是“下”电梯都停在原地。如果没有 visited 数组遇到 k[i]0 的楼层BFS 会把当前楼层反复入队形成死循环。即使没有死循环也可能让答案变得不优在某层原地踏步一次步数增加了但你明明可以直接跳过这个操作。所以代码里对每个节点只访问一次这个“一次”在 k[i]0 时尤其重要。我在实际测试里给 k[i] 全部置 0 的数据跑过如果不加 visited程序直接卡死加上 visited 后只要目标楼层不是这个原地层就正常返回 -1 或正确步数。5.2 起点等于终点别忘了输出 0另一个容易被忽略的输入是 A B。按 BFS 的逻辑初始化 dist[A]0入队后取队首时发现 cur B直接返回 0所以代码不用特判。但如果你写的不是 BFS而是类似“先扩展再判断”的写法就可能把答案算成 1 或直接出错。这种边界情况的通用处理方式在算法开始前先判断 A B如果是直接输出 0。虽然 BFS 本身能处理但显式判断能让你的代码在面对改写成其他算法时更安全。5.3 越界判断的顺序不要乱我见过一些写法是先计算 up 和 down不做边界检查就访问 k[up] 或 k[down]导致数组越界运行时炸掉。正确顺序一定是先检查 nxt 是否在 [1, n] 内再决定是否访问它。这里还有一个细节是计算 up 和 down 时nxt 有可能超出 int 范围吗本题 N 最大 200k[i] 也是 int 范围但理论上如果数据范围放大到 10^9 的楼层数cur k[cur] 可能溢出。稳妥的做法是用 long long 存储中间值或者在做加法前先判断边界。P1135 不需要但这是一种好习惯。5.4 用随机小数据验证比盯着代码看更有效我调试搜索题时最常用的是“对拍”思路写一个非常暴力的 DFS不加剪枝只适合小数据然后和 BFS 的答案对比。比如随机生成 N10 的数据k[i] 随机取 0 到 10A 和 B 随机取 1 到 10跑 1000 组比较两份代码的输出是否一致。如果发现不一致就把那组数据打印出来手动模拟一遍往往很快就能定位问题。有一次我就是这样发现自己的 DFS 剪枝写错了我更新 best[cur] 的条件写成了cnt best[cur]才更新结果把更差路径记成了最优直接 WA。这种逻辑错误靠眼睛很难看出来但对拍一跑就现形了。5.5 个人调试顺序先写暴力再优化最后改复杂算法如果你刚接触搜索题我建议的练习顺序是先用最直观的 BFS 写一版保证过题然后写一版 DFS 剪枝对比两者在随机数据上的表现最后再尝试双向 BFS。这个顺序能帮你建立很重要的直觉同一道题不同算法的代码形态差别很大但最终答案应该一致。当你能做到“换一种算法答案还是那个答案”时你对搜索的理解才算真正到位了。我自己做完 P1135 之后最大的收获不是学会了一个 BFS 模板而是记住了“在无权图上求最短步数第一次访问即是答案”这条铁律。后来的迷宫问题、单词变换问题本质上都是这个套路换了一层皮。希望这篇题解对你也有同样的作用。

洛谷P1135奇怪电梯：从图论建模到BFS/DFS剪枝与双向BFS全解析

相关推荐

深度学习框架选型与模型部署实战：Keras、TensorFlow、PyTorch全解析

artcraft：用工程化流程实现可复现的艺术创作

概率方向论文投稿PEIS期刊全流程实战经验分享

更多资讯

随机森林实战指南：Python sklearn实现与调参避坑全解析

基于华为云ModelArts的模型训练与部署全流程实践

Qwen-Image-2.1云端部署实战：从环境搭建到API服务与成本优化

C#上位机如何用OpenCvSharp实现USB摄像头H264录像

开单软件二维码收款怎么用？从动态二维码到自动对账全解析

MFC集成HALCON实现笔记本摄像头实时采集显示全流程

今日更新

Susi AI API实战指南：susi_alexa_skill如何用Node.js调用chat.json获取智能回答

换新电脑了？KeyStats 恢复码数据找回完全指南，端到端加密统计一键重建

重建二叉树：由前序与中序遍历序列还原二叉树的原理与 Java 实现（YCBlogs 剑指 Offer 精讲）

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？