奇怪的电梯

题意

有一栋楼一共 N 层，电梯一开始在 A 楼，目标是到 B 楼。

在第 i 层时，电梯只能尝试两种移动：

上到 i + K_i
下到 i - K_i

如果超出 1..N 范围，对应按钮就失灵。

要求输出从 A 到 B 最少要按几次按钮；如果到不了，输出 -1。

思路

最直接的做法是从起点开始 DFS，枚举所有可能的跳法，只要能到终点就更新最优答案。

这个版本很好理解：

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, s, t;
int k[MAXN];
bool vis[MAXN];
int ans = 1e9;

void dfs(int u, int step) {
    if (step >= ans) {
        return;
    }
    if (u == t) {
        ans = step;
        return;
    }

    int v1 = u + k[u];
    int v2 = u - k[u];

    if (v1 >= 1 && v1 <= n && !vis[v1]) {
        vis[v1] = true;
        dfs(v1, step + 1);
        vis[v1] = false;
    }
    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);

    if (ans == (int) 1e9) {
        cout << -1 << '\n';
    }
    else {
        cout << ans << '\n';
    }

    return 0;
}

但它会重复搜索很多楼层状态。

把楼层看成图上的点

这题其实非常适合图论建模。

把每一层看成一个点，那么从第 i 层最多能向两个点连边：

i + K_i
i - K_i

而每按一次按钮，代价都相同，都是 1。

于是整题就变成了：

无权图最短路。

为什么 BFS 就够了

在无权图中，BFS 会按距离从小到大扩展节点。

所以某层楼第一次被访问到时，当前记录的按钮次数就是到它的最少次数。

对于这题来说，每层最多只有两条出边，写起来也很简单。

正式做法

建一个 dista[i]，记录起点到第 i 层的最少按钮次数；
初始全部设为 -1；
起点入队，距离设为 0；
每次弹出当前楼层，尝试上下两个跳法；
若目标楼层第一次被访问到，答案就是它的距离。

Python 知识

在跳跃数组前补一个 0，让楼层编号可以直接作为下标，减少反复 -1 转换。
(floor-k[floor], floor+k[floor]) 用元组直接产生当前层的两个邻居。
distance 同时承担访问标记和最短距离，初值 -1 表示尚未访问。
/home/rainboy/mycode/hugo-blog/content/program_language/python/bfs_shortest.md：BFS 中用距离结构兼作 visited。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：deque 的队列操作。

代码

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/**
 * 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-07-28 15:52
 */

#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 可以向上或向下移动
        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);
        }
    }

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

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17from collections import deque


n, start, target = map(int, input().split())
jumps = [0] + list(map(int, input().split()))
distance = [-1] * (n + 1)
distance[start] = 0
queue = deque([start])

while queue:
    floor = queue.popleft()
    for nxt in (floor - jumps[floor], floor + jumps[floor]):
        if 1 <= nxt <= n and distance[nxt] == -1:
            distance[nxt] = distance[floor] + 1
            queue.append(nxt)

print(distance[target])

复杂度

时间复杂度： $O(N)$
空间复杂度： $O(N)$

总结

这题是一个很标准的“建图 + BFS”入门题。

只要看出“每层是点、按钮是边、每次代价都一样”，就能直接套无权图最短路模板。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

把楼层看成图上的点

为什么 BFS 就够了

正式做法

Python 知识

代码

复杂度

总结

一图流解析