分析:
提取关键字,至少,所以本题用bfs来解。
每一个电梯都有可以运动的步长,而且只能是这么长,所以我们要到达目的地要尝试在别的楼层转乘电梯,用bfs来暴力破解,达到楼层后立即返回,这个就不会超时。
代码:
#include<stdio.h>
struct point{
int place;
int step;
};
int book[500];//标记已经走过的路线
int n,aim;//n为楼高,aim为目标楼层
int end=0;//队尾
struct point queue[100000];//队列
int move[300];//每层楼的步长,也是我们移动的依据
int bfs()
{
int front=0;
while(front<end)
{
if(queue[front].place==aim) return queue[front].step;
struct point goup,godown;
goup.place=queue[front].place+move[queue[front].place];
godown.place=queue[front].place-move[queue[front].place];
if(goup.place<=n&&!book[goup.place]) {
book[goup.place]=1;
goup.step=queue[front].step+1;
queue[end++]=goup;
}
if(godown.place>0&&!book[godown.place]){
book[godown.place]=1;
godown.step=queue[front].step+1;
queue[end++]=godown;
}
++front;
}
return -1;
}
main()
{
struct point start;
scanf("%d%d%d",&n,&start.place,&aim);
for(int i=1;i<=n;i++)
{
scanf("%d",move+i);
}
book[start.place]=1;
start.step=0;
queue[end++]=start;
printf("%d",bfs());
//printf("\n");
// for(int i=0;i<end;i++)
// {
// printf("place=%d step%d\n",queue[i].place,queue[i].step);
// }
}