56 lines
1.7 KiB
C++
56 lines
1.7 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
int n; //n层楼
|
||
int a; //从a层
|
||
int B; //到b层
|
||
const int N = 100010;
|
||
const int INF = 0x3f3f3f3f;
|
||
int K[N]; //k数组表示第一层出现的数字k[i]
|
||
int st[N]; //这个楼层是不是已经到达过,防止在深度优先搜索时走回头路，那就是个死循环，这点很重要
|
||
int res = INF; //最优步数
|
||
|
||
//floor表示当前搜到的楼层,step表示已经切换过的次数
|
||
void dfs(int floor, int step) {
|
||
// 减枝，对于已经超过已知最短路径的分支，不用再继续探索，就算是后面可以成功到达b，也不可能比已知路径短。
|
||
// 不加这句，会有两个点的TLE
|
||
if (step > res) return;
|
||
|
||
//如果成功到达b楼，那么对比一下本次的步数与最优步数的大小，小的保留
|
||
//递归的出口
|
||
if (floor == b) {
|
||
res = min(res, step);
|
||
return;
|
||
}
|
||
|
||
//标识本楼层走过了
|
||
st[floor] = 1;
|
||
|
||
//上不越界就搜
|
||
int x = floor + k[floor];
|
||
if (x <= n && !st[x]) dfs(x, step + 1);
|
||
|
||
//下不越界就搜
|
||
int y = floor - k[floor];
|
||
if (y >= 1 && !st[y]) dfs(y, step + 1);
|
||
|
||
//回溯.标识本楼层未走过
|
||
st[floor] = 0;
|
||
}
|
||
|
||
int main() {
|
||
//输入
|
||
cin >> n >> a >> b;
|
||
for (int i = 1; i <= n; i++) cin >> k[i];
|
||
|
||
//标识已使用
|
||
st[a] = 1;
|
||
|
||
//深搜,从楼层a出发，已经走了0步
|
||
dfs(a, 0);
|
||
|
||
//如果所有的分支全部走完，但没有机会到达b楼层，那么,res就不会变改写，就一直是INF，依此判断是否不可达
|
||
if (res != INF) printf("%d", res);
|
||
else printf("-1");
|
||
return 0;
|
||
} |