首页 > 代码库 > A strange lift
A strange lift
A strange lift |
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
Total Submission(s): 941 Accepted Submission(s): 448 |
Problem Description 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 5 1 53 3 1 2 50 |
Sample Output 3 |
Recommend 8600 |
/*莫名其妙就WA,莫名就AC*/#include <bits/stdc++.h>#define N 205using namespace std;int Floor[N];int visit[N];int step[N];int n,A,B;int bfs(){ queue<int> Q; Q.push(A); visit[A]=1; while(!Q.empty()) { int start=Q.front(); //cout<<start<<endl; Q.pop(); if(start==B) return step[B]; if(start+Floor[start]<=n&&!visit[start+Floor[start]]) { //cout<<"visit[start][0]="<<visit[start][0]<<endl; Q.push(start+Floor[start]); visit[start+Floor[start]]=1; step[start+Floor[start]]=step[start]+1; } if(start-Floor[start]>=1&&!visit[start-Floor[start]]) { Q.push(start-Floor[start]); visit[start-Floor[start]]=1; step[start-Floor[start]]=step[start]+1; } } return -1;}int main(){ //freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin); while(scanf("%d",&n)!=EOF&&n) { memset(visit,0,sizeof visit); memset(step,0,sizeof step); scanf("%d%d",&A,&B); for(int i=1;i<=n;i++) { scanf("%d",&Floor[i]); } printf("%d\n",bfs()); }}
A strange lift
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。