今天在刷洛谷 P1135「奇怪的电梯」的时候忽然想通了一个以前一直没在意的细节为什么那么多题解里数组都要开到 N1数据老老实实从下标 1 开始存。以前总觉得这就是个个人习惯无伤大雅直到这次把样例从一组扩到多组亲手被边界问题坑了几次才真正体会到这个小习惯有多省事。这篇文章我就把这道题从头到尾拆一遍题目到底在说什么、为什么它本质上是一个最短路问题、BFS 怎么写、以及“从下标 1 开始存数据”到底妙在哪里。新手可以直接照着代码敲老手也可以看看自己在边界处理上有没有踩过同款坑。1. 题目拆解奇怪的电梯到底在问什么1.1 题意与输入输出格式先还原一下题目。假设一栋大楼有 N 层你一开始在第 A 层目标是去第 B 层。每一层楼的电梯按钮旁边都写着一个数字 Ki表示这一层的电梯按钮只能让你做两件事之一向上走 Ki 层向下走 Ki 层。但有一个限制无论向上还是向下目标层必须落在 1 到 N 之间否则这个按钮按了也没用。问从 A 层到 B 层最少需要按几次按钮如果永远到不了输出 -1。输入格式很直观第一行是三个正整数 N、A、B第二行是 N 个整数 Ki依次表示第 1 层到第 N 层的按钮数字。注意这里题目自己就说了“第 i 层楼上的数字”天然就是 1-based 的编号。标准样例长这样5 1 5 3 3 1 2 5输出是 3。怎么来的1 楼按钮是 3向上到 4 楼4 楼按钮是 2向下到 2 楼2 楼按钮是 3向上到 5 楼。路径就是 1 → 4 → 2 → 5正好按下 3 次按钮。1.2 为什么叫“奇怪的电梯”这题的“奇怪”在于每一层楼上的 Ki 只决定你能跳多远但你并不知道往哪个方向跳更优。你站在第 i 层能看到的信息只有“向上 iKi”“向下 i-Ki”这两个候选但哪一个能更快接近目标完全看不出来。这其实和你平时坐电梯的直觉完全不同。真实电梯里你想去 5 楼你会去按一个写着 5 的按钮但在这道题里你按下按钮之后去哪一层完全由“出发楼层”决定不由你的意志决定。所以整个搜索过程更像是在走迷宫电梯的每一次移动都受到当前楼层数字的约束而不是受你目的地的约束。更严谨一点说这栋楼可以被抽象成一张有向图楼层 1 到 N 是这张图的 N 个节点从节点 i 出发如果 iKi 在 1~N 范围内就有一条边指向节点 iKi如果 i-Ki 在范围内也有一条边指向节点 i-Ki每条边的权重都是 1代表“按一次按钮”。于是原问题就变成了一个非常经典的问题在一张无权有向图上求从节点 A 到节点 B 的最短路径长度。到这里“奇怪的电梯”就不再奇怪了它就是一个披着生活场景外衣的 BFS 板子题。1.3 题目考察的核心能力这道题放在算法学习里想考察的并不是什么高深的技巧主要是三件事第一能不能识别出“最少操作次数 每次操作代价相同”的组合并联想到底层结构是图。只要想到图BFS 几乎是自动浮出来的方案。第二能不能处理好边界条件。向上和向下都会越界越界的分支直接剪掉。这个判断只要漏掉一个“ N”或者“ 1”程序就可能在运行时出现诡异行为。第三能不能把楼层编号和数组下标正确对应。这也是我整篇文章最想强调的地方。楼层编号从 1 开始那么在数组里就应该让下标 1 对应第 1 层而不是强行从 0 开始给自己添堵。所以这道题表面上是搜索题实际上也是“数据结构基本功”的试金石。2. 数组从下标 1 开始存储的妙处2.1 为什么坚持用 k[1] 表示第 1 层很多编程语言里数组天然从 0 开始所以不少人在读入 Ki 的时候习惯这样写for (int i 0; i n; i) { cin k[i]; // k[0] 存的是第 1 层 }诚实地讲这种写法不是不行。你完全可以维护一个“下标 i 对应楼层 i1”的映射搜索时把楼层号减一再用。真正的问题在于当代码变长、样例变多以后这种手工偏移很容易出错。出错的方式还非常隐蔽。举个例子队列里弹出来的 cur 是楼层号 4你想访问 4 楼的按钮数字。如果按从 0 存储的习惯你得写 k[cur - 1]而不是 k[cur]。写的时候精神高度集中可能没问题但一旦你在某个分支里直接写了 k[cur]程序不会立刻报错而是取到了错误的按钮数字搜索结果就会随机性地对、随机性地错。这种 bug 在单组样例下可能侥幸通过一旦样例增加立刻原形毕露。反过来从下标 1 开始存储k[cur] 就是第 cur 层的按钮k[1] 就是第 1 层的按钮。楼层号就是下标下标就是楼层号中间没有任何转换层。搜索代码里你甚至不需要想一想“这里要不要减一”直接把队列里弹出的节点当作数组下标用就行。2.2 两种写法的对比我把两种写法的核心代码摆在一起你们感受一下差别。从 1 存储的写法// 数组开大一位 int k[MAXN]; for (int i 1; i n; i) { cin k[i]; // 第 i 层楼存到 k[i] } int cur q.front(); q.pop(); int up cur k[cur]; // 直接读不需要偏移 int down cur - k[cur];从 0 存储的写法int k[MAXN]; for (int i 0; i n; i) { cin k[i]; // k[i] 对应第 i1 层楼 } int cur q.front(); q.pop(); int realFloor cur 1; // 先把“下标”转回“楼层” int up realFloor k[cur]; int down realFloor - k[cur];表面上看第二种也就多写了一行损失不大。但在实际比赛或者刷题环境下这些多余的转换会持续消耗你的注意力而且在边界判断时特别容易心态失衡。比如判断 up 是否越界时你用的是 realFloor k[cur] 跟 N 比还是直接用 cur k[cur] 跟 N 比如果这里稍一混乱写成了 cur k[cur] N但队列里存的是下标而不是楼层那边界判断就是错的。从 1 存储的核心思想是让“数据表达”和“业务语义”保持一致。楼层这个概念天然从 1 开始数那就别硬把它掰成 0 开始。很多有经验的竞赛选手在开数组时都会习惯性地多开几个位置目的就是为了让下标直接对应题目的编号体系。这不是洁癖这是降低认知负担的实用技巧。2.3 样例增加后更能体现这种妙处标题里专门提到“样例增加”这不是随便写的。我自己实测下来数据从 0 存储的代码在做单组样例时往往一遍就对了因为人脑在短代码里可以手动完成偏移校正。但当你开始连续跑十几组样例尤其是目标楼层在边界附近、每组数据 N 还不同的时候从 0 存储的代码就会开始出现各种“间歇性”错误。典型的症状是这组样例输出是对的下一组样例突然多了一个 1再下一组又对了。排查半天发现原来是有一段代码在某些分支里用了 k[cur]另一些分支里用了 k[cur-1]而 cur 恰好落在不同区间时错误不会触发。这种 bug 用调试器都难抓因为它的错误依赖具体数据。从 1 存储的代码就没有这种困扰。队列里存的是楼层号数组下标直接就是楼层号所有分支用的都是同一个 k[cur]。同一个变量同一个语义不管样例怎么增加都不会出现“同一份代码里混用两套下标体系”的情况。我给一个非常简单的建议只要题目里出现了“第 1 到第 N”这种编号数组就开 N1下标范围 1~N下标 0 永远空着不用。你就当这个位置不存在只把 1 到 N 号位置当作有效空间。这个习惯一旦养成能帮你规避掉一大类低级 bug。3. BFS 解法求最短路径的经典套路3.1 为什么这里首选 BFS 而不是 DFS很多人拿到这道题第一反应是写 DFS因为递归搜索看起来直观。但 DFS 有一个致命缺陷它找到的第一条路径不一定是步数最少的路径。你可能会想那就把所有路径都搜一遍取最小值好了。这当然可以但在最坏情况下这种暴力搜索会反复访问大量节点指数级膨胀甚至栈溢出。BFS 不一样。BFS 的特点是逐层扩展先访问距离起点为 1 的所有节点再访问距离为 2 的所有节点。当边权全部为 1 时BFS 第一次“碰到”目标节点时的层数就一定是最少步数。这在图论里是教科书级别的结论无权图上的最短路径BFS 就是最优解。从图上理解也很简单BFS 的队列天然维护了“距离从小到大的访问顺序”你不需要记录任何路径长度做比较第一次到达即最优。这比 DFS 加回溯干净利索得多。3.2 从 1 存储的 BFS 完整代码这里我给一份 C 版本风格偏竞赛注释写得比较细。#include bits/stdc.h using namespace std; const int MAXN 205; int n, a, b; int k[MAXN]; // k[i] 表示第 i 层的按钮数字下标从 1 开始 bool vis[MAXN]; // 访问标记防止同一层被重复入队 int main() { cin n a b; for (int i 1; i n; i) { cin k[i]; // 第 1 层存到 k[1]第 n 层存到 k[n] } // 起点等于终点直接返回 0不需要按任何按钮 if (a b) { cout 0 endl; return 0; } queueint q; q.push(a); vis[a] true; // step 数组记录“从起点到当前层按了多少次按钮” vectorint step(n 1, 0); while (!q.empty()) { int cur q.front(); q.pop(); int up cur k[cur]; // 向上走 k[cur] 层 int down cur - k[cur]; // 向下走 k[cur] 层 // 向上走目标层必须在 1~n 范围内 if (up n !vis[up]) { vis[up] true; step[up] step[cur] 1; if (up b) { cout step[up] endl; return 0; } q.push(up); } // 向下走同理不能小于 1 if (down 1 !vis[down]) { vis[down] true; step[down] step[cur] 1; if (down b) { cout step[down] endl; return 0; } q.push(down); } } // 队列都弹完了还没到目标说明不可达 cout -1 endl; return 0; }这套代码的核心逻辑其实只有三句话取出队首节点计算两个候选楼层合法且未访问就入队并更新步数。因为使用了 vis 数组每个楼层最多入队一次复杂度是 O(N) 级别对 200 层这种数据规模来说毫无压力。3.3 Python 版本的实现如果你用 Python 刷题逻辑完全一样只是队列换成了 collections.deque。顺手把 step 数组初始化为 -1这样既能记录步数又能充当访问标记省掉一个布尔数组。import sys from collections import deque def solve(): data sys.stdin.read().strip().split() if not data: return n, a, b map(int, data[:3]) # 关键k[0] 占位不用k[1] 对应第 1 层 k [0] list(map(int, data[3:3 n])) if a b: print(0) return # step[i] -1 表示从未访问过否则记录到达 i 层的最少步数 step [-1] * (n 1) step[a] 0 q deque([a]) while q: cur q.popleft() # 两个方向一起处理用元组遍历更简洁 for nxt in (cur k[cur], cur - k[cur]): if 1 nxt n and step[nxt] -1: step[nxt] step[cur] 1 if nxt b: print(step[nxt]) return q.append(nxt) print(-1) if __name__ __main__: solve()Python 版本里最值得注意的就是那一行k [0] list(...)。这个前导的 0 就是专门用来占住下标 0 的让 k[1] 成为真正的“第 1 层的按钮数字”。很多 Python 初学者会困惑为什么这里要加一个 0实际上目的只有一个让数组下标和楼层编号完全对齐。3.4 处理 Ki 0 的情况防止死循环这道题原题的数据范围里Ki 是可以取 0 的。如果某层楼的按钮数字是 0那么向上和向下的结果都是原地不动。如果没有 vis 数组帮忙挡住队列弹出这一层时会把这一层再次入队形成一个永远跳不出去的自循环整个程序就卡死了。所以无论 Ki 是不是可能为 0vis 数组都必须写。而且要注意起点也要标记为已访问。有人会在 BFS 开头忘记做vis[a] true导致起点被重复入队虽然大部分时候不会死循环但逻辑上不严谨很容易在特殊数据下翻车。我个人的建议是BFS 的访问标记一定要“入队即标记”而不是“出队再标记”。入队时就把 vis 置为 true能有效防止同一个节点被多个方向同时加入队列从而保证每个节点只处理一次。如果你写成出队时标记同一个节点可能已经在队列里排了两份步数计算也会乱。4. 换个视角这题也是最短路问题的入门模型4.1 建图思路每层楼是一个节点BFS 已经能解决这道题了但如果你学图论学到后面再回头看这道题会有不一样的感觉。它本质上就是一个无权有向图的最短路问题BFS 只是这个问题的特化解法。建图逻辑很简单。V 是 {1, 2, ..., N}每个节点 i 至多有两条出边i → i k[i]前提是 i k[i] 在 1 到 N 内i → i - k[i]前提是 i - k[i] 在 1 到 N 内。每一条边的权重都是 1因为按一次按钮算一个单位的代价。目标则是求从节点 A 到节点 B 的最短路径。如果未来题目改一改比如不同楼层的按钮有多有少、按下不同楼层花费的时间不同那 BFS 就不够用了得换成 Dijkstra 或者 SPFA。但“建图”这个思维过程是完全一致的。这也是为什么我建议初学者在做这道题时不要只满足于背出 BFS 模板而是多想想“为什么 BFS 能解决它”。4.2 Dijkstra 风格的非标准实现严格来说边权都为 1 时上 Dijkstra 是杀鸡用牛刀但拿它练手建图也是一个不错的选择。这里我写一个简化版直接用 C 优先队列模拟 Dijkstra 的过程方便以后迁移到加权图场景。#include bits/stdc.h using namespace std; const int MAXN 205; const int INF 0x3f3f3f3f; int n, a, b; int k[MAXN]; int dist[MAXN]; int main() { cin n a b; for (int i 1; i n; i) cin k[i]; memset(dist, 0x3f, sizeof(dist)); dist[a] 0; // pair当前距离, 楼层号优先队列默认是大顶堆所以反着存距离 priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, a}); while (!pq.empty()) { auto [d, cur] pq.top(); pq.pop(); if (d ! dist[cur]) continue; // 旧数据跳过 if (cur b) break; // 目标出队距离已确定 int nxt cur k[cur]; if (nxt n dist[nxt] d 1) { dist[nxt] d 1; pq.push({dist[nxt], nxt}); } nxt cur - k[cur]; if (nxt 1 dist[nxt] d 1) { dist[nxt] d 1; pq.push({dist[nxt], nxt}); } } cout (dist[b] INF ? -1 : dist[b]) endl; return 0; }这段代码里dist[nxt] d 1就是 Dijkstra 的松弛操作。由于所有边权都是 1这个形式看起来有点像 BFS 的 step1但意义不同Dijkstra 是在允许不同权重的前提下不断用更小的距离去更新邻居。我之所以把这份代码也放出来是希望大家看到两种解法在结构上的相似性。BFS 用队列Dijkstra 用优先队列BFS 第一次到达即最优Dijkstra 出队时距离才最终确定。理解了这一点以后遇到“电梯按钮有不同等待时间”之类的变种题你就能自然地过渡到 Dijkstra而不是重新学一遍。4.3 这类模型还能迁移到哪些题目“奇怪电梯”这种“每层只能跳到固定偏移位置”的模型其实是很多搜索题的母题。比如青蛙跳台阶问题每次可以跳若干步问最少跳几次数字华容道类的拼图搜索每个状态是图上的一个节点迷宫问题里带“传送门”或“单向滑动”的变体打开轮盘锁问题每个状态相当于图上的节点转动一次相当于走一条边。它们的共同点都是把每一种“局面”看作一个节点把“一次操作”看作一条边然后求最短路径。所以「奇怪的电梯」虽然简单但它把 BFS、图建模、边界处理、数组下标这一整套基本功全部串起来了是一道性价比特别高的训练题。5. 常见问题与排查技巧实录5.1 程序陷入死循环怎么排查如果你发现程序跑起来不输出结果大概率是访问标记出了问题。最常见的是两种情况。一是起点忘了标记。起点不标记的话第一次从队列弹出起点时会把起点再次放进队列但因为有 step 数组或者 vis 数组通常会在第二次弹出时被挡住但如果你的代码里根本不写访问数组只是纯暴力搜索那就会无限递归或者无限循环。二是 Ki 0 的自环问题。遇到这种层向上和向下都回到自身。如果没有访问标记这一层会被无限地入队、出队、再入队程序就会卡住。排查方法很简单在循环里加一个计数器看看循环次数是否明显大于节点数或者直接断点打印每次出队的楼层号看到同一个楼层反复出现就能确认是被自环卡住了。5.2 越界访问不报错反而让你更慌这个坑我真的是踩到过。在 C 里数组越界属于未定义行为它不一定会崩溃有时候会读到相邻内存里的随机值。于是你的程序表现就是“时好时坏”某些样例答案对了某些样例莫名其妙输出一个巨大的数或者输出随机结果。在 Python 里更阴间列表的负数下标是合法的所以当你想访问 k[cur-1] 却写成 k[cur] 且 cur 是 0 时Python 不会报错而是默默返回最后一个元素。想象一下你为了从 0 存储而下意识地给楼层号减一但边界条件下减成了 -1程序不仅没炸还用数组末尾的值继续算最后给出一个看着合理、实则全错的答案。这种 bug 最难定位因为它不中断、不报错、结果也不是明显离谱。对策就一条所有数组访问前先确认下标在合法区间。如果队列里存的是楼层号那么 k[floor] 合法当且仅当 1 floor n。写越界判断的顺序也很重要我建议先判断楼层是否越界再访问数组不要反过来。5.3 输出始终比答案大 1 或小 1有些读者会碰到“答案老是大 1”的问题。这通常出在步数初始化逻辑上。如果你把起点步数初始化为 0每次扩展时加 1那么第一次扩展到目标时输出 step[target] 就是正确答案。但如果你把起点也计了一次按钮或者拿了 step[cur] 没有加 1 就直接赋值给邻居步数就会错位。建议用一个简单样例手推一遍起点是不是终点如果起点就是终点应该输出 0。这个特判很多人会漏漏了之后答案恰好比正确答案大 1。5.4 快速问题排查速查表我把上面提到的问题整理成一个表方便你以后遇到类似表现时快速定位。现象可能原因快速定位方法程序卡住不结束访问标记缺失或 Ki 0 形成自环打印每次出队的楼层号观察是否有重复偶尔对、偶尔错从 0 存储导致下标偏移混乱检查所有 k 数组访问处确认是否统一用楼层号当下标Python 访问 k[负数] 不报错但结果错城市边界判断写反或漏写在访问数组前打印 cur 和 n确认是否出现 0 或负值答案总是比期望大 1起点终点的特判缺失或起点步数多算了 1单独用 a b 的样例测试输出 -1 但肉眼能看到可行路径向上或向下方向的边界判断有误把合法分支剪掉了手推一遍样例每遍历一层就把候选楼层打印出来5.5 最后一个细节先判越界再判访问我写 BFS 时固定一个顺序先判断候选楼层是否在 [1, N] 内再判断这个楼层是否访问过。if (up n !vis[up]) { ... }顺序别看反了。如果你先判断!vis[up]而 up 刚好是越界的负数在 C 里访问 vis[-1] 是未定义行为可能会莫名其妙地返回 true 或者 false导致分支错误。在 Python 里step[-1] 会访问到列表最后一个元素同样会干扰判断。把范围判断放在第一优先级既是为了逻辑正确也是为了安全。这个顺序习惯在我写过的几乎所有 BFS 题里都适用属于那种“没人强调但非常关键”的细节。回到开头的话题我现在的习惯已经彻底固化凡是题目里的节点编号从 1 开始数组必开 N1下标 0 永远空着。这个习惯最初就是从「奇怪的电梯」这道题里学到的之后刷迷宫、刷图论题、刷各种带编号的模拟题都再也没因为“第几层”和“第几个”搞混而返工。你可以把这个当作一个手到擒来的技巧但我更建议你理解它背后的逻辑让代码里的每一个数字都和题目里说的话一一对应。数据从下标 1 开始存储不是玄学就是最朴素的“少做一道转换少踩一堆坑”。