PP4909 奇怪的电梯（入门）

解题思路

第一步，理解题意。 电梯在第 i 层只能上、下 k[i] 层，问从 A 层到 B 层最少按几次按钮，到不了输出 -1。

第二步，选择算法。 要求"最少按键次数"，每个楼层是一个节点，按一次按钮就从一层走到相邻可达的一层，这是典型的无权图最短路，用广度优先搜索（BFS）最合适，第一次到达的层数一定是最少次数。

第三步，写 BFS。 用数组 d[x] 记录从起点到第 x 层的最少按键次数，初始为 -1。把起点入队并设 d[a]=0。每次从队首取出 x，计算 up=x+k[x] 和 down=x-k[x]，只要没有越界且还没访问过，就更新次数并入队。

第四步，提前结束。 如果取出的就是目标层 b，直接跳出循环，此时 d[b] 就是答案。

边界情况。 如果 A 和 B 相同，一次也不用按，答案是 0。如果 BFS 结束后 d[b] 仍是 -1，说明到不了，输出 -1。

看样例。 1 楼按上到 4 楼，4 楼按下到 2 楼，2 楼按上到 5 楼，共 3 次，输出 3。

参考代码

// P4909 奇怪的电梯 BFS：从 A 层到 B 层最少按几次按钮
#include <iostream>
using namespace std;
int k[205]; // 每层楼上的数字
int d[205]; // d[x] 从起点到 x 层需要按的次数
int que[205]; // 手写队列
int main() {
    int n, a, b, i, head = 0, tail = 0;
    cin >> n >> a >> b;
    for (i = 1; i <= n; i++) cin >> k[i];
    for (i = 1; i <= n; i++) d[i] = -1; // 初始都到不了
    d[a] = 0;
    que[tail++] = a;
    while (head < tail) {
        int x = que[head++];
        if (x == b) break; // 到达目标层
        int up = x + k[x], down = x - k[x];
        if (up <= n && d[up] == -1) { d[up] = d[x] + 1; que[tail++] = up; }
        if (down >= 1 && d[down] == -1) { d[down] = d[x] + 1; que[tail++] = down; }
    }
    cout << d[b] << endl; // 到不了就是 -1
    return 0;
}

复杂度分析

时间复杂度是 O(N)（每层最多访问一次），空间复杂度也是 O(N)。N≤200，非常轻松。