题目大意:输入三个数,n,a,b,n代表n层楼(总高度),a代表现在的位置,b代表目标楼层,然后输入n个数,代表这n层楼每层的按钮,如果改按钮会使电梯不在这n层楼的范围内,则该按钮失效,即没反应,也就是不能按该按钮,然后找出最少要按几下;
思路:bfs,题目理解的话就很简单,注意到达第几层就按第几层的按钮,不是一个个按下来!
代码如下:
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
int vis[300],k[300],flag,n;
typedef struct
{
int x,size;
}cas;
void bfs(int a,int b)
{
cas now,next;
queue<cas>que;
int i,j;
while(!que.empty())
que.pop();
now.x=a;
now.size=0;
vis[now.x]=1;
que.push(now);
while(!que.empty())
{
now=que.front();
que.pop();
if(now.x==b)
{
printf("%d\n",now.size);
flag=0;
return ;
}
for(i=1;i>=-1;i-=2)
{
next.x=now.x+i*k[now.x];
if(next.x<1||next.x>n||vis[next.x])
continue;
vis[next.x]=1;
next.size=now.size+1;
if(next.x==b)
{
printf("%d\n",next.size);
flag=0;
return ;
}
que.push(next);
}
}
return;
}
int main()
{
int a,b,i;
while(~scanf("%d",&n)&&n)
{
scanf("%d%d",&a,&b);
for(i=1;i<=n;i++)
scanf("%d",&k[i]);
memset(vis,0,sizeof(vis));
flag=1;
bfs(a,b);
if(flag)
printf("-1\n");
}
return 0;
}