HDU 1548 A strange lift 搜索[通俗易懂]

HDU 1548 A strange lift 搜索

大家好,又见面了,我是全栈君。

A strange lift

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11341    Accepted Submission(s): 4289

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

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

#define N 205
int v[N],c[N];
int n,a,b,t;

struct node 
{
    int i,time;
};

void bfs(int x)
{
    node now,tmp;
    queue<node>  q;
    now.i=x,now.time=0;
    memset(v,0,sizeof(v));
    q.push(now);
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(now.i==b)
        {
            t=0;
            cout<<now.time<<endl;
            return ;
        }
        for(int k=0;k<2;k++)
        {
            if(k==0)   tmp.i=now.i+c[now.i];
            if(k==1)   tmp.i=now.i-c[now.i];
            if(tmp.i>0&&tmp.i<=200&&!v[tmp.i])
            {
                v[tmp.i]=1;
                tmp.time=now.time + 1;
                q.push(tmp);
            }
        }
    }
}

int main()
{
    while(cin>>n)
    {
        if(n==0)  break;
        cin>>a>>b;
        for(int k=1;k<=n;k++)
            cin>>c[k];
        t=1;
        bfs(a);
        if(t)  cout<<-1<<endl;
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115634.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 协程

    协程介绍协程:是单线程下的并发,又称微线程,纤程。英文名Coroutine。一句话说明什么是线程:协程是一种用户态的轻量级线程,即协程是由用户程序自己控制调度的。、需要强调的是:对比操作系统控制

  • 智能避障小车_单片机智能小车程序

    智能避障小车_单片机智能小车程序      接下来我对所用的模块以及小车的硬件部分做一个讲解        小车的总体效果图如下:      首先是模块简介:            1、首先就是L298N,这是一个经典的电机驱动,相信基本所有玩过单片机,玩过电机的人都使用过,它可以最高容忍15v电压输入,逻辑电平2.4-5.5v,所以使用单片机的3.3v完全可以驱动,它并没有PWM接口来控制电机的速度,只能使逻辑电平输出…

    2022年10月17日
  • 【Themes for IntelliJ-based IDEs】Idea主题下载

    【Themes for IntelliJ-based IDEs】Idea主题下载下载地址:https://plugins.jetbrains.com/search?isPaid=false&tags=Theme下载完成后直接将.jar拖入到idea中即可

  • eth挖矿显卡的选择_挖矿一般用什么显卡

    eth挖矿显卡的选择_挖矿一般用什么显卡以太坊显卡挖矿指南1.显卡篇挖矿靠显卡核心计算,所以AMD显卡比NVIDA卡更高效。选择AMD卡,要求显卡显存大于2G,推荐购买4G显存显卡.目前市面上可购选择的显卡品牌型号还有速度.蓝宝石-影驰-技嘉-索泰-讯景-微星-迪兰-盈通#显卡型号操作系统挖矿速度驱动版本显卡功耗

  • Jquery 插件库

    Jquery 插件库

  • anycast技术「建议收藏」

    anycast技术「建议收藏」转载别人的,不好意思啊浅析AnyCast网络技术什么是BGPAnyCast?BGPanycast就是利用一个(多个)as号码在不同的地区广播相同的一个ip段。利用bgp的寻路原则,短的aspath会选成最优路径(bgp寻路原则之n),从而优化了访问速度。其实bgpanycast是不同服务器用了相同的ip地址。阿里的DNS就是使用了BGPAn…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号