先说个题外话我给学生讲这道“奇怪的电梯”时十有八九会有人问“这题到底哪里奇怪了”其实题名只是唬人真正有意思的是它背后那个数据结构层面的小细节——下标。如果你去各大OJ搜这道题名字基本统一叫“奇怪的电梯”题面也就几行但做过的人都知道样例看着平平无奇真自己动手写却容易挂在边界和下标换算上。标题里特意带上“样例增加”我猜很多同学已经感受到了样例变多之后原来那套“反正小数据随便写写”的思路立刻崩了。这篇就把这道题从头到尾拆开重点聊聊为什么要从下标1开始存数据以及怎么把这个习惯用到其他搜索题里去。适合刚学完BFS、正在刷图论入门题的人也适合被各种奇奇怪怪边界条件折磨过的竞赛新手。1. 先搞懂电梯的规则这不是模拟题是隐藏的图论题1.1 题面浓缩后到底在说什么楼层一共有N层编号从1到N。每一层有一个数字Ki表示这一层电梯按钮能带着你移动的层数。你站在第i层只能按一次按钮然后要么向上走Ki层要么向下走Ki层当然越界的情况不能走。现在给你起点A和终点B问最少按几次按钮能到。到不了就输出-1。乍一看这像是一道“模拟走路”的题从A出发每次有两个选择走到B就停。换个说法这就是从一个状态出发不断扩展到相邻状态直到找到目标状态顺便统计步数。但凡在这种“最短路”题里看到“只能选一个方向走固定步数”的描述第一反应就应该是BFS而不是DFS或者什么高深的数学推导。因为每按一次按钮步数加一所有边的权值都是1BFS天然能保证第一次搜到终点时的步数最少。有个经典认知误区是有人看到“每层只能上或下Ki层”就开始想用递推或者模拟循环觉得只要沿着某个方向一直加加加减减减总能到。实际上电梯不像人走路你走到某一层之后下一步能去哪完全由那一层的Ki决定而且顺序可以任意绕。比如样例里从1楼出发可能先上到4楼又从4楼下到2楼再从2楼上到5楼路径完全不是单调的。1.2 为什么是BFS而不是DFSDFS也能做但很容易出事。如果你用深度优先搜索去硬跑会陷入非常深的递归而且DFS找到的第一条路并不一定是最短路。虽然可以加一个当前步数的剪枝让找到的解优于当前最优才继续但在这类“每个点可以来回走”的图上DFS的搜索树会非常难看时间复杂度可能指数爆炸。BFS就舒服很多每一层楼层在搜索中最多入队一次因为你只要第一次到达某个楼层就已经拿到了从起点到这一层的最短步数后面再绕回来只会更长没有意义。用一个visited数组标记“这个楼层是否已经访问过”整个复杂度就是O(N)空间也是O(N)。这也是为什么我坚持认为所有“最少步数”“最短路径”且边权为1的问题直接进入BFS的思考框架就行。提示有人会想着用Dijkstra没有必要。Dijkstra能处理边权不同的情况但这里每条边都算1次按钮BFS的先进先出特性天然一层一层往外扩展根本不需要优先队列。2. 从下标0到下标1这个“土办法”能省掉一半的烦恼2.1 为什么竞赛题里老有人强调“从1开始存”很多第一次接触算法题的人会非常不适应明明数组下标从0开始是语言层面的规则为什么一堆题解却把数据从下标1开始放这恰恰是竞赛里一个约定俗成的习惯。原因是这类题的题目描述永远从1开始编号第1层楼、第2个节点、编号为1到N的点。如果你用0-based存储那么“第i楼”在数组里就是k[i-1]所有代码里都要带一个“-1”一旦循环里写high了非常容易在判断边界时出bug。而1-based存的写法是“第i楼的数据就是k[i]”和你嘴上念的、纸上画的全对得上。举个小例子BFS扩展时当前楼层cur向上走k[cur]层新楼层是cur k[cur]向下走是cur - k[cur]。如果改用0-based当前楼层在数组里的编号是idx对应真实楼层是idx1你扩展时很容易搞成idx k[idx]再加回1或者漏了某个转换环节。调试这种代码时你脑子得同时维护“真实楼层”和“数组下标”两套数据出错率成倍上升。2.2 用占位符实现“下标对齐楼层号”在Python里数组本身只能从0开始但这不妨碍你手动空出第0位。最优雅的写法就是读入时在列表最前面塞一个0k [0] list(map(int, input().split()))这样k[1]就代表第1层的Kik[n]代表第n层的Ki。唯一的代价是k[0]永远闲置但换来的是代码里可以毫无顾虑地写k[cur]不用管任何下标偏移。C更直接直接在全局区开数组const int MAXN 205; int k[MAXN];然后从k[1]开始读数据k[0]空着不用。有人觉得浪费一个int空间但这对算法题来说根本不值一提反而是代码正确性的保险。很多老手在写图论题时连邻接表、并查集、树状数组都统一用1-based就是为了让“节点的编号”和“数据的下标”始终保持同一套语义。2.3 这个习惯的深层价值状态和编号保持同构下标从1开始不只是为了省一个“-1”。更深层的好处是当你把“楼层编号”直接当成数组下标时状态本身就有了天然的映射关系。判断一个楼层有没有访问过直接查vis[nxt]记录步数直接写step[nxt]。不需要再写一堆函数去转换“数组坐标”和“实际位置”之间的映射。生活化一点这就像你给学生编号学号是1号到40号你如果非要用0号到39号来存储那查“3号学生”就得记着去数组第2个位置找。平时没事紧张的时候或者数据量一大的时候真的是自己给自己埋雷。反过来舍掉第0号位置让学号和下标完全对齐你的代码就变成了一本可以直接照着念的名册。注意如果你用的是Python记得n1长度的vis和step数组也要同步创建[False] * (n 1)和[-1] * (n 1)让下标一直对齐到n。我见过有人用[False] * n存最后访问vis[n]时直接下标越界就是没想清楚占位符的问题。3. 完整实现C和Python双版本直接可以抄的作业3.1 核心数据结构与流程这道题需要的东西非常少一个数组存每层电梯能走的层数k一个bool数组vis做去重一个整数数组step记录从起点到每个楼层的最短步数外加一个队列。整个BFS流程大概是这样的起点a入队vis[a]标记为已访问step[a]设为0。不断从队头取出当前楼层cur。如果cur已经是终点b直接输出step[cur]程序结束。计算两个候选楼层cur k[cur]和cur - k[cur]。对于每个候选楼层nxt先判断是否在1到N范围内再看是否没访问过都满足就更新vis、step并入队。队列空了还没到终点说明根本不存在可行路径输出-1。关键在于第5步的顺序先判范围再判访问缺一不可。如果你先访问了越界下标轻则读到一个垃圾值重则直接数组越界崩溃。如果你不判访问BFS会在两个楼层之间来回横跳队列越来越长最后超时。3.2 C代码#include bits/stdc.h using namespace std; const int MAXN 205; int k[MAXN]; bool vis[MAXN]; int step[MAXN]; int main() { int n, a, b; scanf(%d%d%d, n, a, b); // 下标从1开始读取k[0]空着不用 for (int i 1; i n; i) { scanf(%d, k[i]); } queueint q; q.push(a); vis[a] true; step[a] 0; while (!q.empty()) { int cur q.front(); q.pop(); if (cur b) { printf(%d\n, step[cur]); return 0; } // 向上走 int nxt cur k[cur]; if (nxt 1 nxt n !vis[nxt]) { vis[nxt] true; step[nxt] step[cur] 1; q.push(nxt); } // 向下走 nxt cur - k[cur]; if (nxt 1 nxt n !vis[nxt]) { vis[nxt] true; step[nxt] step[cur] 1; q.push(nxt); } } printf(-1\n); return 0; }代码里MAXN开成205是因为题目N一般不超过200。实际写的时候建议开大一点比如205、210都行别跟边界较劲。3.3 Python代码from collections import deque n, a, b map(int, input().split()) # 占位技巧列表前塞一个0让下标和楼层编号对齐 k [0] list(map(int, input().split())) vis [False] * (n 1) step [-1] * (n 1) q deque([a]) vis[a] True step[a] 0 while q: cur q.popleft() if cur b: break for nxt in (cur k[cur], cur - k[cur]): if 1 nxt n and not vis[nxt]: vis[nxt] True step[nxt] step[cur] 1 q.append(nxt) print(step[b])Python这份代码用了一个小技巧两个候选楼层用元组遍历省掉两段重复的if。step数组初始化为-1如果BFS结束还没更新过step[b]就直接输出-1。如果起点就是终点第一次从队列里取出a时就breakstep[a]是0输出0逻辑没问题。3.4 复杂度与空间开销时间上每个楼层最多入队一次每次出队处理两个方向所以是O(N)。空间上开了三个长度为N的数组加一个队列也是O(N)。对N200这种数据规模来说闭着眼写随便过。但如果哪天题目把N调到10的5次方甚至10的6次方这套写法依然成立只需要把MAXN和数组大小改大索引和判断逻辑完全不用变这就是1-based存储带来的可迁移性。实操心得我调试这类BFS时会把step数组当作调试利器。每当想确认某条路径是怎么走出来的可以在入队时打印一句printf(from %d to %d, step%d\n, cur, nxt, step[nxt]);。小规模样例一打印整个搜索顺序一目了然。4. 样例增加以后边界数据才是真正的试金石4.1 经典样例的手动推演最常见的样例是5层楼从1楼到5楼每层对应3、3、1、2、5。我们手动跑一遍起点1楼k[1]3向上到4楼所以第一次入队的是4楼。出队4楼k[4]2向上6楼越界自动忽略向下到2楼入队。出队2楼k[2]3向下-1楼越界忽略向上到5楼入队。出队5楼正好是终点此时步数记录为3。路径是1 - 4 - 2 - 5三次按钮。这就是为什么BFS能在第3层扩展时碰到终点也说明路径中途完全可以“绕路”。如果你用贪心想法一直往上走1 - 4 - 6越界反而走不到所以“每一步有两个选择”这个状态模型的建立特别重要。4.2 自己动手增加样例5个必须验证的边界场景样例增加不是平台的事做题时更该自己给自己加样例。你至少得验证下面这些情况场景输入示例预期输出备注起点就是终点3 2 2 / 1 1 10不需要按按钮只有一层楼1 1 1 / 50必须处理k[1]很大但越界的情况楼层连续跳远10 1 10 / 9 1 8 2 7 3 6 4 5 5见调试路径往往绕过多个楼层完全不可达3 1 3 / 1 1 100-1k[3]超出楼层范围向上越界4 2 4 / 1 2 2 222楼向上到4楼直达这些边界样例的价值在于它们逼你把“nxt 1 nxt n”这个条件写对。尤其是一层楼的情况如果你忘了判断访问vis[6]这种下标C里就是未定义行为Python里直接IndexError。交了OJ后WA还好说运行时错误才是真的头疼。4.3 我踩过的坑样例能过提交全错说个真实的翻车经历。早期我写这道题时用的是0-based存储int数组存了0到n-1层的k值然后BFS里判断边界写成了0 nxt nxt n。本地跑平台给的样例由于样例恰好对称输出居然是对的。但提交后WA声一片。后来我定位了很久才发现问题真实的目标楼层是b而我用0-based存的时候终点变成了b-1。有一次b恰好是nb-1就是n-1刚好落在数组内程序不会崩但输出永远比正确值少1或者多1。这就是典型的“样例太仁慈”没覆盖到所有情况。标题里那句“样例增加”我深有体会如果一开始就给了“N1”或者“AB”的样例我相信写错的人会少一半。注意写这道题时永远记住一件事——题面里出现的每个楼层号如果要直接当数组下标用请把数组偏移到1开始或者老老实实在所有地方做减一转换。最怕的是代码里一半用真实楼层、一半用数组下标自己混着混着就晕了。5. 从一个电梯题扩展出去状态搜索的意识才是重点5.1 这类题的共同模板“奇怪的电梯”其实是一类问题的缩影给定一个状态每次可以从当前状态通过若干合法操作转移到一些新状态问最少操作次数。这类问题在竞赛里太常见了比如迷宫寻路每个坐标是一个状态上下左右是转移。单词变换每次改一个字母问最少改几次到目标单词。开锁问题四位密码锁每次旋转一位。倒水问题两个容器互相倒问能否量出指定水量。它们的共同点都是“状态图上的无权最短路”。BFS解决的就是这套通用流程状态定义、转移规则、访问标记、步数记录。你在一维电梯上理解了这套流程之后做二维、三维、甚至状态压缩的题目思路都是一以贯之的。5.2 下标1存储的迁移价值在树状数组、线段树、并查集这些数据结构里1-based存储几乎是“标准配置”。树状数组的i lowbit(i)直接依赖下标从1开始并查集的父节点数组也是把元素编号和数组下标一一对应。提前在BFS这道题里养成1-based的习惯后面学这些数据结构会顺利很多。有人说“Python里用1-based感觉怪怪的列表本来从0开始”但真正写起来你会发现[0]占位符已经成了许多竞赛选手心照不宣的常规操作。读入一行数字前面加0再遇到“编号从1到N”的题直接照单全收这里面的好处你写多了自然就有肌肉记忆了。还有一个小技巧如果题目的状态不是连续整数而是一个二维坐标比如迷宫里的(x, y)那么下标1-based的映射同样适用只要把行列号从1开始计数边界判断就从0 nx n变成了1 nx n配合题目描述更直观。5.3 对新手的一些务实建议如果你现在刚开始刷题我给你的建议是不要太早追求“省空间”“骚操作”先把最朴素的BFS框架写得滚瓜烂熟。做这道“奇怪的电梯”时试着把上面C、Python两份代码都手打一遍不要复制粘贴。打完再把样例走一遍然后自己写几个边界样例用纸笔画一下搜索顺序再回来对照代码里每一步对应哪个判断。这一步看起来笨但确实能把BFS的框架、visited数组的作用、边界判断的意义一次性钉在脑子里。后面遇到再复杂的搜索题人家讨论的是什么优化什么剪枝你脑子里至少有个稳稳的底座。实操心得我在教学生的时候要求他们每写一道BFS题必须回答三个问题1. 状态是什么2. 从一个状态能转移到哪些状态3. 什么情况下不用再访问这三个问题想清楚了代码其实只是填空。电梯题的状态就是“当前楼层”转移就是上下两个方向不用再访问就是“这个楼层已经有过更短或等长的路径到达过”。6. 收个尾这道题给我留下最深的三个感受第一数组下标绝对不是小事。一个“从1开始存还是从0开始存”的决策直接影响你代码能不能一遍过。我见过太多人不是不懂BFS而是被下标换算搞到心态爆炸。竞赛不是比谁更会炫技而是比谁在细节上更稳。第二样例增加是对思维懒惰的打脸。一个样例只能代表一条路径边界条件才是真正决定代码质量的东西。每次看到题目说“样例增加”的时候我反而会高兴因为这相当于出题人在善意地提醒大家别以为样例过了就没事了多想想边界。第三BFS的框架值钱状态建模更值钱。把“奇怪的电梯”理解成一个状态转移问题之后你会发现很多题表面上花里胡哨骨子里都是同一套东西。以后遇到什么奇怪的传送门、奇怪的按钮、奇怪的密码锁第一反应都该是这不就是另一个“奇怪的电梯”嘛。
