2511: 【普及/提高-】【P1135】奇怪的电梯
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：5
解决：4
题目描述
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 层楼（）上有一个数字 （）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： 代表了 （，，……），从 楼开始。在 楼，按“上”可以到 楼，按“下”是不起作用的，因为没有 楼。那么，从 楼到 楼至少要按几次按钮呢？
输入
共二行。
第一行为三个用空格隔开的正整数，表示 （，）。
第二行为 个用空格隔开的非负整数，表示 。
输出
一行，即最少按键次数，若无法到达，则输出
-1。样例输入 复制
5 1 5
3 3 1 2 5样例输出 复制
3提示
对于 的数据，，，。
#include<bits/stdc++.h>
using namespace std;
struct node {
int floor, d; //队列中记录的层数和按钮次数
};
queue<node> Q; // 广度优先搜索的队列
int n,a,b;
int k[1000],vis[1000]; //每层楼上下可以跳跃几层，以及是否访问过
int main(){
cin>>n>>a>>b;
for (int i=1;i<=n;i++)
cin>>k[i];
Q.push((node){a, 0}); //将初始元素加入到队列
vis[a] = 1; //记录初始楼层已访问过
node now;
while (!Q.empty()) {
now = Q.front();
Q.pop();
if (now.floor == b) break; // 找到目标解
for (int sign = -1; sign <= 1; sign += 2) { // sign枚举-1和1
int dist = now.floor + k[now.floor] * sign; // 目标楼层，sign为1是上
if (dist >= 1 && dist <= n && vis[dist]==0) {
// 如果按按钮能到达的楼层有效并且未访问过该楼层
Q.push((node){dist, now.d + 1});
vis[dist] = 1; // 该楼层为已访问过
}
}
}
if (now.floor == b) // 找到目标解
cout << now.d << endl;
else // 无法到达
cout << -1 << endl;
return 0;
}