F. A strange lift
Time Limit:1000ms
Case Time Limit:1000ms
Memory Limit:32768KB
Font Size:
+
-
There is a strange lift.The lift can stop can at every floor as you want, and there is a number Ki(0 <= Ki <= N) on every floor.The lift have just two buttons: up and down.When you at floor i,if you press
the button "UP" , you will go up Ki floor,i.e,you will go to the i+Ki th floor,as the same, if you press the button "DOWN" , you will go down Ki floor,i.e,you will go to the i-Ki th floor. Of course, the lift can't go up high than N,and can't go down lower
than 1. For example, there is a buliding with 5 floors, and k1 = 3, k2 = 3,k3 = 1,k4 = 2, k5 = 5.Begining from the 1 st floor,you can press the button "UP", and you'll go up to the 4 th floor,and if you press the button "DOWN", the lift can't do it, because
it can't go down to the -2 th floor,as you know ,the -2 th floor isn't exist.
Here comes the problem: when you is on floor A,and you want to go to floor B,how many times at least he havt to press the button "UP" or "DOWN"?
Input
The input consists of several test cases.,Each test case contains two lines.
The first line contains three integers N ,A,B( 1 <= N,A,B <= 200) which describe above,The second line consist N integers k1,k2,....kn.
A single 0 indicate the end of the input.
Output
For each case of the input output a interger, the least times you have to press the button when you on floor A,and you want to go to floor B.If you can't reach floor B,printf "-1".
Sample Input
Sample Output
3
BFS的裸题。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctype.h>
#include<cmath>
#include<queue>
#include<stack>
#define INF 1000000
using namespace std;
int n,a,b;
int lift[250]={0};
struct node
{
int x,s;
};
int in(int x)
{
if (x>0 && x<=n) return 1;
return 0;
}
int bfs()
{
if (a==b) return 0;
int visit[250]={0};
queue<node> q;
node temp;
temp.x=a;
temp.s=0;
visit[a]=1;
int tx,ty;
q.push(temp);
node now;
while(!q.empty())
{
node t=q.front();
q.pop();
if (t.x==b) return t.s;
tx=t.x+lift[t.x];
ty=t.x-lift[t.x];
if (in(tx) && !visit[tx])
{
visit[tx]=1;
now.x=tx;
now.s=t.s+1;
q.push(now);
}
if (in(ty) && !visit[ty])
{
visit[ty]=1;
now.x=ty;
now.s=t.s+1;
q.push(now);
}
}
return -1;
}
int main ()
{
int i,j,k;
while(scanf("%d",&n)!=EOF)
{
if (n==0) break;
scanf("%d%d",&a,&b);
for (i=1; i<=n; i++)
scanf("%d",lift+i);
int s=bfs();
cout<<s<<endl;
}
return 0;
}
分享到:
相关推荐
富士lift变频器软件Lift3.1.0Setup.rar
Simply_Lift.pdf scala框架lift的get start
官网下载慢 需要的拿去
下载了很久,下载自https://lift.cs.princeton.edu/java/windows/网速异常的慢,下载时间2021/01/26,需要的自取
zoj 2837 Left Library Lift.md
Lift探索.Lift 是一个好框架,能构建引人入胜的web 应用的。Lift 简单灵活的框架设计能够轻松使用一些强大的 技术(如 Comet、Ajax),这虽然听上去象陈词滥调,但以我们的经验,Lift 能让开发者更关注开发中有趣的 ...
53小波提升的编解码代码,可用于图像的53小波变换
I have been writing Lift and Scala for 4 years, and even I learn new things about the language and the framework on a weekly basis. Please consider Lift an path and an exploration, rather than an end...
81、1360:奇怪的电梯(lift)-2020.02.23a
DoubleLift,sequentially按顺序扩展和折叠布局的水平和垂直方向,博客附件,效果请查看博客相对应项目
..........................................................59 Dissecting the Program....................................................................60 Choosing a Message Box ....................
用于访问 Lift.do API 的 Ruby 库。 由于还没有正式的 API,这个库使用了未记录的移动应用程序 API。 安装 将此行添加到应用程序的 Gemfile 中: gem 'liftapp-client' 然后执行: $ bundle 或者自己安装: $...
变频器说明书系列-KEB F5-Lift-CN.pdf
变频器说明书大全系列-FRN-Lift-CN.rar
变频器说明书大全系列-KEB F5-Lift-CN.rar
施耐德-电梯专用变频器ATV71-Liftpdf,施耐德电梯专用变频器ATV71-Lift说明: 一个界面友好的图形操作终端 ATV71 的高级中文图形操作终端可以快速设置变频器的各种功能,使之能够 很容易地使用: 1). 可定制的图形...
Scissor lift built from a library of parameterized, reusable components, with a hydraulic actuator.
富士电机电梯专用变频器FRENIC-Lift系列样本pdf,本资料是关于富士电机电梯专用变频器FRENIC-Lift系列样本,更多详细内容请点击下载!
The.Definitive.Guide.To.Lift[2009][EN][PDF]
Built on top of the Scala JVM programming language, Lift takes a different—yet ultimately easier—approach to development than MVC frameworks such as Rails. Each recipe in this book includes a ...