49 lines
1.3 KiB
C++
49 lines
1.3 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 100010;
|
||
typedef pair<int, int> PII;
|
||
int n; //n层楼
|
||
int a; //从a层
|
||
int B; //到b层
|
||
int K[N];//k[i]数组,描述i层楼，可以向上+向下几层楼(如果不出界的话)
|
||
int st[N];
|
||
queue<PII> q;
|
||
int step = -1;
|
||
|
||
void bfs() {
|
||
//将初始化结点入入队列
|
||
q.push({a, 0});
|
||
|
||
//地球不爆炸，我们不放假
|
||
while (!q.empty()) {
|
||
//套路
|
||
PII p = q.front();
|
||
q.pop();
|
||
//到达b楼，输出结果
|
||
if (p.first == b) {
|
||
step = p.second;
|
||
break;
|
||
}
|
||
//尝试两种可能，上和下,这个-1至+1，步长为2用的好啊！
|
||
for (int i = -1; i <= 1; i += 2) {
|
||
//下一次到达的可能楼层
|
||
int nx = p.first + k[p.first] * i;
|
||
//如果没有出界，并且，记录过的最优解需要更新的话
|
||
if (nx >= 1 && nx <= n && st[nx] == 0) {
|
||
st[nx] = 1;
|
||
q.push({nx, p.second + 1});
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
//输入
|
||
cin >> n >> a >> b;
|
||
for (int i = 1; i <= n; ++i) cin >> k[i];
|
||
//广度优先搜索
|
||
bfs();
|
||
printf("%d", step);
|
||
return 0;
|
||
} |