1360：奇怪的电梯(lift)时间限制: 1000 ms 内存限制: 65536 KB 提交数: 4790 通过数: 2047 【题目描述】大楼的每一层楼都可以停电梯，而且第i层楼（1≤i≤N）（1≤i≤N） 上有一个数字Ki(0≤=Ki≤=N）Ki(0≤=Ki≤=N） 。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： 【输入】共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200,1≤A,B≤N)N,A,B(1≤N≤200,1≤A,B≤N) ，第二行为NN 个用空格隔开的正整数，表示KiKi 。 【输出】一行，即最少按键次数,若无法到达，则输出−1−1 。 【输入样例】5 1 5 3 3 1 2 5 【输出样例】3 【来源】
|
#include <bits/stdc++.h>
#define MAXN 305
using namespace std;
struct node
{int x;int step;node(){x=0,step=0;}
};
queue<node> que;
int arr[MAXN];
int vis[MAXN];
int n,a,b;void bfs(int x)
{node p,q,n1,n2;p.x=x;vis[x]=1;p.step=0;que.push(p);bool flag=false;while(!que.empty()){q=que.front();que.pop();int xx=q.x;if(xx==b){flag=true;cout<<q.step<<endl;break;}n1.x=xx+arr[xx];n1.step=q.step+1;n2.x=xx-arr[xx];n2.step=q.step+1;if(n1.x>=1&&n1.x<=b&&!vis[n1.x]){que.push(n1),vis[n1.x]=1;}if(n2.x>=1&&n2.x<=b&&!vis[n2.x]){que.push(n2),vis[n2.x]=1;}}if(!flag)cout<<"-1"<<endl;return ;
}int main()
{int i;cin>>n>>a>>b;for(i=1; i<=n; i++)cin>>arr[i];bfs(a);return 0;
}
![[Codeforces Round #644 (div3)]1360](https://img-blog.csdnimg.cn/20200527021330301.png)
