奇怪的电梯

问题描述

小H有一个奇怪的电梯，电梯可以根据需要停在每个楼层，每个楼层上都对应一个数字$K_i$（0 <= $K_i$ <= N），该电梯只有两个按钮："UP"和"DOWN"。在第i层楼，如果按下"UP"按钮，电梯将移动到$i+K_i$层；如果按下"DOWN"，电梯将移动到$i-K_i$层。当然，电梯有一个移动的范围，不能高于N且不能低于1。例如，有一个5层楼的建筑物，$k_1 = 3，k_2 = 3，k_3 = 1，k_4 = 2，k_5 =5$。从一楼开始，按"UP"按钮，将上升到四楼，如果按"DOWN"按钮，电梯将无法移动，因为它不能下降到-2楼。
现在问题来了：小H想从A层移动到B层，他至少要按几次"UP"或"DOWN"按钮，你能帮帮他嘛？

输入格式

输入包含多个测试用例。每个测试用例包含两行。
第一行包含上述三个整数N，A，B（1 <= N，A，B <= 200），第二行包含N个整数$k_1，k_2，.... k_n$。
若读取到单个0，则表示输入结束

输出格式

对于每个测试用例，输出一个整数表示最少按下"UP"或"DOWN"按钮的次数，若无法到达B层，请输出"-1"。每个测试用例的输出占一行。

样例输入

5 1 5
3 3 1 2 5
0

样例输出

3

数据规模和约定

1<=N,A,B<=200,0<=$k_i$<=N

提示

隐式图问题

#include <bits/stdc++.h>
using namespace std;

int k[205];
bool arrived[205];

struct loucen {
    int censu, step;
    loucen(int censu, int step) : censu(censu), step(step) {}
};

void bfs(int a, int b, int n) {
    queue<loucen> q;
    q.push(loucen(a, 0));
    arrived[a] = true;
    while (!q.empty()) {
        loucen now = q.front();
        if (now.censu == b) {
            printf("%d\n", now.step);
            return;
        }
        q.pop();
        // up
        auto &t = now.censu;
        if (t + k[t] <= n && !arrived[t + k[t]]) {
            q.emplace(loucen(t + k[t], now.step + 1));
            arrived[t + k[t]] = true;
        }
        // down
        if (t - k[t] >= 1 && !arrived[t - k[t]]) {
            q.emplace(loucen(t - k[t], now.step + 1));
            arrived[t - k[t]] = true;
        }
    }
    printf("-1\n");
}

int main() {
    int n, a, b;
    while (scanf("%d ", &n) == 1 && n != 0) {
        scanf("%d %d ", &a, &b);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &k[i]);
            arrived[i] = false;
        }
        bfs(a, b, n);
    }

    return 0;
}