算法题：电梯

问题描述

有一天PJY做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1≤i≤N)上有一个数字K；(0≤K~i~≤N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了K~i~ (K~1~=3，K~2~=3，…)，从一楼开始。在一楼，按“上，”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？

输入格式

第1行为三个正整数，表示N,A,B(1≤N≤200，1≤A,B≤N)；
第2行为N个正整数，表示K~i~。

输出格式

1行，即最少按键次数，若无法到达，则输出-1。

样例

输入

5 1 5
3 3 1 2 5

输出

3

数据范围

对于100% 的数据，1≤N≤200，1≤A,B≤N，0≤Ki​≤N。

解决方案

思路

广度优先搜索

代码

#include <iostream>
#include <queue>

using namespace std;

struct Layer {
    int index;
    int ans = 0;
};

int main() {
    int n, a, b;
    int arr[205];
    static int vis[205];
    cin >> n >> a >> b;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }

    queue<Layer> q;
    Layer l;
    l.index = a;
    q.push(l);

    while (!q.empty()) {
        l = q.front();
        q.pop();

        if (l.index == b) {
            break;
        }

        int index = l.index - arr[l.index];
        if (index >= 1 && vis[index] == 0) {
            vis[index] = 1;
            Layer ll;
            ll.index = index;
            ll.ans = l.ans + 1;
            q.push(ll);
        }

        index = l.index + arr[l.index];
        if (index <= n && vis[index] == 0) {
            vis[index] = 1;
            Layer ll;
            ll.index = index;
            ll.ans = l.ans + 1;
            q.push(ll);
        }
    }

    if (l.index == b)
        cout << l.ans;
    else
        cout << -1;

    return 0;
}