奇怪的电梯
题目描述
呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第 $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;
}