奇怪的电梯

题目描述

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

输入格式

共二行。

第一行为三个用空格隔开的正整数，表示 $N, A, B$（$1 \le N \le 200$，$1 \le A, B \le N$）。

第二行为 $N$ 个用空格隔开的非负整数，表示 $K_i$。

输出格式

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

样例 #1

样例输入 #1

5 1 5
3 3 1 2 5

样例输出 #1

3

提示

对于 $100 \%$ 的数据，$1 \le N \le 200$，$1 \le A, B \le N$，$0 \le K_i \le N$。

//暴力的方法，会被卡，完美AC要用bfs
//指数型枚举——选上或者下，两种情况
//优化一下 //每层楼最多走一次取到的方案 一定比 某层楼走过两次以上的方案 要好  //运用全排列思想—选过就不能再选了
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 10010;

int n, A, B;
int evlt[N];  //存当前电梯楼层允许上或者下的楼数
int res = 1e9;  //答案
bool st[N];  //存每层楼走没走过

//x表示当前在几楼
void dfs(int x, int cnt){
    if(cnt >= res) return ;
    if(x < 0 || x > n) return ;

    if(x == B){
        res = min(res, cnt);  //去最优解
        return ;
    }

    st[x] = true;

    //上楼
    if(x + evlt[x] <= n && !st[x + evlt[x]]){
        st[x + evlt[x]] = true;
        //printf("x + evlt[x] = %d\n", x + evlt[x]);
        dfs(x + evlt[x], cnt + 1);
        st[x + evlt[x]] = false;  //恢复现场
    }

    //下楼c
    if(x - evlt[x] > 0 && !st[x - evlt[x]]){
        st[x - evlt[x]] = true;
        //printf("x - evlt[x] = %d\n", x - evlt[x]);
        dfs(x - evlt[x], cnt + 1);
        st[x - evlt[x]] = false;  //恢复现场
    }
}

int main()
{
    scanf("%d%d%d", &n, &A, &B);
    for(int i = 1; i <= n; i++){
        scanf("%d", &evlt[i]);
    }

    dfs(A, 0);
     if(res == 1e9){
        printf("-1\n");
        return 0;
    }
    printf("%d\n", res);
    return 0;


}