bfs入门（HDU - 1548）A strange lift

客官°小女子只卖身不卖艺 2023-08-17 15:40 86阅读 0赞

# A strange lift #

题目链接：[https://vjudge.net/problem/HDU-1548\#author=Zerpro][https_vjudge.net_problem_HDU-1548_author_Zerpro]

题目：

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
    题意：
    有一天桐桐做了一个梦，梦见了一种很奇怪的电梯。
     大楼的每一层楼都可以停电梯，而且第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<iostream>
    #include<queue>
    #include<cstring>
    #include<cstdio>
    //#include<bits/stdc++.h>
    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<node>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<<bfs()<<endl;
        }
    
       return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11161421.html

[https_vjudge.net_problem_HDU-1548_author_Zerpro]: https://vjudge.net/problem/HDU-1548#author=Zerpro