A strange lift
题目链接:
题目:
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 are on floor A,and you want to go to floor B,how many times at least he has to press the button "UP" or "DOWN"?5 1 53 3 1 2 50Sample Output
3 题意: 有一天桐桐做了一个梦,梦见了一种很奇怪的电梯。 大楼的每一层楼都可以停电梯,而且第i层楼(1≤i≤N)上有一个数字K;(0≤Ki≤N)。 电梯只有四 个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。 例如:3 3 1 2 5代表了Ki (K1=3,K2=3,…),从一楼开始。在一楼,按 “上” 可以到4楼,按 “下” 是不起作用的,因为没有-2楼。 那么,从A楼到B楼至少要按几次按钮 呢? 思路:bfs,见下方代码详细注释
//// Created by hjy on 2019/7/10.//#include#include #include #include //#include using namespace std;typedef long long ll;struct node{ int x; int dept;};//结构体存储位置和步数int A,B;//起点和终点int book[205];//记录是否走过int put[205];//存储题给数组数值int n;//多少层int bfs(){ queue qu;//以结构体压入队列中 node now,next;//建立现在状态和下一步状态 now.x=A; now.dept=0;//现在状态的起始位置是A,步数为0; book[A]=1;//起始位置走过 qu.push(now);//将起始位置压入队列中 while(!qu.empty()) { now=qu.front();//现在状态为队首的状态 qu.pop();//删除队首,进行下一步操作 if(now.x==B)//如果走到了B终点状态,返回步数值 return now.dept; for(int i=-1;i<=1;i+=2)//小技巧,上下两个方向,往下走乘以-1,上走乘以1 { next=now;//下一步状态先令他为现在状态 next.x+=(put[next.x]*i);//下一步状态为现在状态加上1乘以或-1乘以原数组该位置的值 if(next.x<=0||next.x>n||book[next.x])//判断是否越界 continue; book[next.x]=1;//下位置就走过了 next.dept++;//步数加一 qu.push(next);//将下一位置压入队列中 } } return -1;//否则返回-1;}int main(){ while(cin>>n&&n) { cin>>A>>B; for(int i=1;i<=n;i++) cin>>put[i]; memset(book,0,sizeof(book));//初始化数组 cout< <