奇怪的电梯

形式化题目

有一栋 $n$ 层的大楼，第 $i$ 层（ $1 \leqslant i \leqslant n$ ）上有一个数字 $k_i$ 。从楼层 $u$ 出发，每次操作只能到达 $u + k_u$ 或 $u - k_u$ ，目标楼层不在 $[1, n]$ 内则这次操作非法。

求从起点 $A$ 到终点 $B$ 的最少操作次数；如果 $B$ 不可达，输出 $-1$ 。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-13 13:19
 * update_at: 2026-08-13 13:19
 */
// brute.cpp：小数据暴力解，把每一步按钮操作看成选择序列来递归枚举。
// 每个递归层代表一次按钮选择（向上或向下），用 vis[] 保证路径不重复访问楼层。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

int n, s, t;            // n: 楼层数, s: 起点楼层, t: 终点楼层
int k[MAXN];            // k[i] 表示第 i 层能向上/向下移动的层数
bool vis[MAXN];         // vis[i] 表示当前路径是否已经到过第 i 层
int ans = 0x3f3f3f3f;   // 当前找到的最少按键次数，初始为无穷大

// 当前在楼层 u，已经按了 step 次按钮。
// 递归的每一层在做一次选择：这次按钮是向上还是向下。
void dfs(int u, int step) {
    if (u == t) {   // 这条路径到达了终点，用它的按键次数更新答案
        if (step < ans) ans = step;
        return;
    }
    if (step >= ans) return;    // 按键次数已经不会比当前答案更优，剪枝

    // 选择 1：向上跳 k[u] 层
    int v1 = u + k[u];
    if (v1 >= 1 && v1 <= n && !vis[v1]) {
        vis[v1] = true;
        dfs(v1, step + 1);
        vis[v1] = false;
    }
    // 选择 2：向下跳 k[u] 层
    int v2 = u - k[u];
    if (v2 >= 1 && v2 <= n && !vis[v2]) {
        vis[v2] = true;
        dfs(v2, step + 1);
        vis[v2] = false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s >> t;
    for (int i = 1; i <= n; i++) {
        cin >> k[i];
    }

    vis[s] = true;
    dfs(s, 0);

    // 一条到达终点的路径都没找到，输出 -1。
    if (ans == 0x3f3f3f3f) {
        cout << -1 << '\n';
    }
    else {
        cout << ans << '\n';
    }
    return 0;
}

这个暴力把每一步按钮操作看成选择序列：每个递归层做一次选择（向上或向下），用 vis[] 保证路径不重复访问楼层，走到终点就更新最少步数。它枚举的是所有简单路径，所以一定找得到最优解，但简单路径数量随 $n$ 指数增长，只适合小数据。

暴力慢在同一个楼层会被反复搜索——而从不同路径第二次到达某个楼层，对求"最少次数"没有任何帮助。关键观察是：每次按键代价都是 1，楼层之间构成一张无权图，而无权图上的最短路就是 BFS：

BFS 按距离分层扩展，先访问距离 0 的点，再访问距离 1 的点……所以某个楼层第一次被访问到时，距离已经最小；
于是让 dista[i] 同时承担"最短距离"和"访问标记"两个角色（-1 表示未访问），每个楼层只入队一次，第一次到达终点时立即输出答案。

以样例 5 1 5、k = [3, 3, 1, 2, 5] 为例，BFS 的过程如下：

出队楼层	尝试	结果	距离
1	+3 → 4	入队	dist[4] = 1
1	-3 → -2	越界，失灵
4	+2 → 6	越界，失灵
4	-2 → 2	入队	dist[2] = 2
2	+3 → 5	入队	dist[5] = 3
2	-3 → -1	越界，失灵
5	终点	输出 3

表格里每一行对应一次按键尝试。注意楼层 5 第一次被访问时距离就是 3，这正是"首次访问即最短"；而楼层 3（ $k_3 = 1$ ）从 4 出发本该能到达，但表中没有它——因为 BFS 先扩展距离更小的路径，且每个楼层只访问一次，这正是避免重复搜索的关键。

实现上不需要建邻接表：从楼层 u 出发的两个邻居就是 u + k[u] 和 u - k[u]，扩展时现场计算，越界或已访问的跳过即可。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-28 15:52
 * update_at: 2026-08-13 13:19
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

int n, s, t;        // n: 楼层数, s: 起点楼层, t: 终点楼层
int k[MAXN];        // k[i] 表示第 i 层能向上/向下移动的层数
int dista[MAXN];    // dista[i] 表示起点到第 i 层的最少按键次数，-1 表示未访问

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s >> t;
    for (int i = 1; i <= n; i++) {
        cin >> k[i];
    }

    // BFS：无权图最短路。楼层第一次被访问到时，距离一定是最短的。
    memset(dista, -1, sizeof(dista));
    queue<int> q;
    dista[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (u == t) {   // 到达终点，直接输出最少按键次数
            cout << dista[u] << '\n';
            return 0;
        }

        // 从当前楼层 u 只能尝试两个方向：向上跳或向下跳 k[u] 层。
        int v1 = u + k[u];   // 向上
        int v2 = u - k[u];   // 向下

        // 越界的按钮失灵；已经访问过的楼层不需要再入队。
        if (v1 >= 1 && v1 <= n && dista[v1] == -1) {
            dista[v1] = dista[u] + 1;
            q.push(v1);
        }
        if (v2 >= 1 && v2 <= n && dista[v2] == -1) {
            dista[v2] = dista[u] + 1;
            q.push(v2);
        }
    }

    // 所有可达楼层都搜索完仍没到终点，说明 B 不可达。
    cout << -1 << '\n';
    return 0;
}

复杂度

时间：每个楼层最多入队一次，每次扩展 $O(1)$ ，总 $O(n)$ 。
空间：距离数组 $O(n)$ ，队列最坏 $O(n)$ ，总 $O(n)$ 。

总结

这道题是最标准的"建图 + BFS"入门题：看出"每层是点、每次按键是边、代价相同"，就变成无权图最短路。BFS 的分层扩展保证首次访问即最短，同时天然避免重复搜索，是图遍历到最短路之间的第一座桥。rbook 的《图的遍历》详细讲解了 DFS/BFS 的分层思想与 visited 标记的作用。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20朴素想法（brute.cpp）
  每个递归层做一次按钮选择：向上 / 向下
  枚举所有不重复访问楼层的简单路径，走到终点更新答案
        |
        | 瓶颈：同一楼层会被反复搜索，简单路径指数增长
        v
关键观察
  每次按键代价相同 -> 楼层之间构成无权图
  无权图最短路 = BFS 分层扩展
        |
        | 首次访问即最短
        v
BFS（main.cpp）
  dista[i] = 起点到第 i 层的最少按键次数，-1 表示未访问
  从 u 扩展两个邻居：u + k[u]（向上）、u - k[u]（向下）
  越界按钮失灵；已访问楼层跳过（每层只入队一次）
  第一次到达终点即输出答案，队列空则输出 -1
        |
        v
复杂度 O(n)，空间 O(n)

图中上方是暴力的"选择序列"模型，它正确但重复；中段的关键观察把问题从"搜索路径"降级为"无权图最短路"；下方 BFS 用"每个楼层只访问一次"同时解决重复搜索和最短性两个问题，这就是 $O(n)$ 复杂度的来源。

目录

形式化题目

思路

代码

复杂度

总结

图示解析