奇怪的电梯(lift)

题目描述

大楼有 $N$ 层，第 $i$ 层写有数字 $K_i$ 。电梯在 $i$ 层时，可上移到 $i+K_i$ （不超过 $N$ ），或下移到 $i-K_i$ （不小于 $1$ ），每次有效移动算一次按键。给定 $N,A,B$ 和序列 $K_{1\dots N}$ ，求从 $A$ 楼到 $B$ 楼的最少按键次数，无法到达输出 $-1$ 。

思路

把每层看成一个顶点，两个按钮看成两条无权有向边，从 $A$ 开始 BFS。dist[i] 记录从 $A$ 到 $i$ 的最少按键次数（ $-1$ 表示未访问），第一次到达 $B$ 时的距离就是答案。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-09-30 07:03
# update_at: 2026-09-30 07:06

import sys
from collections import deque


def fewest_presses(n: int, start: int, target: int, jumps: list[int]) -> int:
    """无权有向图 BFS：返回 start 到 target 的最少按键次数，不可达返回 -1。

    楼层是顶点，第 i 层的「上/下」两个有效按钮是两条代价为 1 的出边，
    所以队列的层号就是按键次数，第一次到达 target 即为最少次数。
    """
    dist = [-1] * (n + 1)  # -1 兼作未访问标记和「不可达」的答案
    dist[start] = 0
    queue = deque([start])
    while queue:
        floor = queue.popleft()
        for nxt in (floor - jumps[floor], floor + jumps[floor]):  # 下 / 上两个按钮
            in_building = 1 <= nxt <= n  # 同时挡掉越界与 K_i = 0 的失效按钮
            if in_building and dist[nxt] < 0:
                dist[nxt] = dist[floor] + 1
                queue.append(nxt)
    return dist[target]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, a, b = next(data), next(data), next(data)
    jumps = [0] + [next(data) for _ in range(n)]  # 1-indexed：jumps[i] 即题面的 K_i

    print(fewest_presses(n, a, b, jumps))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-05 12:00
 * update_at: 2026-10-05 12:00
 */

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

typedef long long ll;

const int MAXN = 205; // 题目数据范围 N <= 200

ll n, a, b;
int k[MAXN];        // k[i] 表示第 i 层楼写的数字
int dist[MAXN];     // dist[i] 表示从 a 到 i 的最少按键次数，-1 表示未访问

queue<int> q;

// 从起点 a 开始 BFS，第一次到达某层即为最少按键次数
void bfs() {
    memset(dist, -1, sizeof(dist));
    dist[a] = 0;
    q.push(a);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        int nxt;
        nxt = u + k[u];
        if (nxt <= n && dist[nxt] == -1) {
            dist[nxt] = dist[u] + 1;
            q.push(nxt);
        }
        nxt = u - k[u];
        if (nxt >= 1 && dist[nxt] == -1) {
            dist[nxt] = dist[u] + 1;
            q.push(nxt);
        }
    }
}

int main() {
    scanf("%lld%lld%lld", &n, &a, &b);
    for (int i = 1; i <= n; i++) scanf("%d", &k[i]);
    bfs();
    printf("%d\n", dist[b]);
    return 0;
}

目录

题目描述

思路

参考代码