- A strange lift https://vjudge.net/problem/HDU-1548
- 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
第一种解法: 使用 BFS, 这里需要考虑到队列中楼层重复的问题, 所有设置了一个 vis 来避免相同数据加入.
- #include <iostream>
- #include<vector>
- #include<bits/stdc++.h>
- #include<queue>
- using namespace std;
- bool vis[210];
- struct node{
- int num;
- int step;
- node (){};
- node(int num,int step){
- this->step= step;
- this->num=num;
- }
- };
- void bfs(int n,int a,int b,node* floor){
- int flag=0;
- memset(vis,0,sizeof(vis));
- queue<node>que;
- node st(a,0) ;
- que.push(st);
- while (!que.empty()){
- node start = que.front();
- que.pop();
- vis[start.num]=1;
- if(start.num==b) {
- cout<<start.step<<endl;
- return;
- }
- for (int i = 0; i <2; i++){
- if(i==0){
- int num = start.num-floor[start.num].num;
- if(num>=1&&num<=n&&!vis[num]) {
- que.push( node(num,start.step+1));
- }
- }
- else{
- int num = start.num+floor[start.num].num;
- if(num>=1&&num<=n&&!vis[num]) {
- que.push(node(num,start.step+1));
- }
- }
- }
- }
- if(!flag)cout<<"-1"<<endl;
- }
- int main(){
- int n,a,b,k;
- while (cin>>n,n>0){
- cin>>a>>b;
- node floor[210];
- for (int i = 1; i <= n; i++){
- cin>>k;
- floor[i].num=k;
- floor[i].step=0;
- }
- bfs(n,a,b,floor);
- }
- }
- View Code
第二种解法: 使用最短路 dijkstra
- #include <stdio.h>
- #include <algorithm>
- #include <cstring>
- #include <cmath>
- #include <queue>
- using namespace std;
- const int N =205;
- const int INF = 9999999;
- int n;
- int graph[N][N];
- int dist[N];
- bool vis[N];
- void dijkstra(int s){
- memset(vis,false,sizeof(vis));
- for(int i=1;i<=n;i++){
- dist[i] = graph[s][i];
- }
- for(int i=1;i<=n;i++){
- int mindis = INF;
- int mark;
- for(int j=1;j<=n;j++){
- if(!vis[j]&&dist[j]<mindis){
- mark = j;
- mindis = dist[j];
- }
- }
- vis[mark] = true;
- for(int j=1;j<=n;j++){
- if(!vis[j]&&dist[j]>dist[mark]+graph[mark][j]){
- dist[j] = dist[mark]+graph[mark][j];
- }
- }
- }
- }
- int main(){
- while(scanf("%d",&n)!=EOF,n){
- int s,t;
- scanf("%d%d",&s,&t);
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++){
- if(i==j) graph[i][j]=0;
- else graph[i][j] = INF;
- }
- }
- for(int i=1;i<=n;i++){
- int num;
- scanf("%d",&num);
- if(i-num>=1) graph[i][i-num] = 1;
- if(i+num<=n) graph[i][i+num] = 1;
- }
- dijkstra(s);
- if(dist[t]>=INF) printf("-1\n");
- else printf("%d\n",dist[t]);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3719147.html