正经题解｜奇怪的电梯

【算法分析】

由于位置的个数很少且要求最小步数，可以考虑从 $A$ 位置开始广搜，同时用一个数组 $d$，$d_i$ 表示从 $A$ 位置到 $i$ 位置需要的步数，最后输出 $d_B$ 即可。

【参考代码】

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

const int maxn = 2e2 + 9;
int d[maxn], k[maxn];
int main() {
    int N, A, B;
    cin >> N >> A >> B;
    for (int i = 1; i <= N; i++) cin >> k[i];
    memset(d, -1, sizeof(d));
    d[A] = 0;
    queue<int> q;
    q.push(A);
    while (q.size()) {
        int r = q.front();
        q.pop();
        if (r + k[r] <= N && d[r + k[r]] == -1) {
            d[r + k[r]] = d[r] + 1;
            q.push(r + k[r]);
        }
        if (r - k[r] >= 1 && d[r - k[r]] == -1) {
            d[r - k[r]] = d[r] + 1;
            q.push(r - k[r]);
        }
    }
    cout << d[B];
    return 0;
}

【时间复杂度】

$O(N)$

【预计得分】

$100pts$