HDU 1548 A strange lift

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 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"?   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 5 3 3 1 2 5 0   Sample Output

3

题目大意：

坐电梯是，输入在每一层都有一个数字Ki（0 <= Ki <= N）。电梯只有两个按钮：上和下。当你在楼层i，如果你按下“UP”按钮，你会上去Ki楼层，也就是说，你会去i + Ki楼层，如果你按下“DOWN”按钮，你会下去Ki楼，即，你会去i-Ki楼。当然，电梯不能上升高于N，并且不能下降到低于1.例如，具有5个楼层的楼层，并且k1 = 3，k2 = 3，k3 = 1，k4 = 2，k5 = 5.从第一层开始，你可以按下“UP”按钮，你会上到4楼，如果你按下“DOWN”按钮，电梯不能它，因为它不能下到-2楼，你知道，-2楼不存在。 这里的问题：当你在A楼，你想去B楼，至少要多少次按下“UP”或“DOWN”按钮？

解题思路：

在这个题中，我们可以采用两种方法，一种是BFS，一种是最短路径算法（迪杰斯特拉等）。再用优先队列时，用bfs从起点开始存入队列开始搜，假设下一个点没有走过而且在1~n层之间，则压入队列。符合条件则输出步数。最短距离的如程序备注所示

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; //迪杰斯特拉法 const int inf = 1<<30; //最大值 int n; int map[205][205]; //映射二维数组 int a[205],cnt; // int vis[205],cast[205]; void Dijkstra(int s,int e)//迪杰斯特拉最短路径算法 { int i,j,min,pos; memset(vis,0,sizeof(vis)); //初始化vis数组 for(i = 0; i<n; i++) //起点位置向周边 { cast[i] = map[s][i]; } cast[s] = 0; //起点位置消耗0 vis[s] = 1; //起始位置访问点设置为1 for(i = 1; i<n; i++) { min = inf; //让最小值最大化 for(j = 0; j<n; j++) { if(cast[j]<min && !vis[j])//从位置开始向周边访问获取最短距离 { pos = j; min = cast[j]; } } if(min == inf) //如果这个最短距离是最大值，则退出 break; vis[pos] = 1; //标志访问过的且是最短距离位置的那个点标志位1 for(j = 0; j<n; j++) { if(cast[pos]+map[pos][j]<cast[j] && !vis[j]) // cast[j] = cast[pos]+map[pos][j]; } } } int main() { int i,j,s,e,x,y; while(~scanf("%d",&n),n) { scanf("%d%d",&s,&e); s--,e--; for(i = 0; i<n; i++) for(j = 0; j<n; j++) map[i][j] = inf; for(i = 0; i<n; i++) { scanf("%d",&a[i]); if(i+a[i]<n) map[i][i+a[i]] = 1; if(i-a[i]>=0) map[i][i-a[i]] = 1; } Dijkstra(s,e); printf("%d\n",cast[e]==inf?-1:cast[e]); } return 0; }