一本通1360 奇怪的电梯

1001-高同学

发表文章数:265

热门标签

首页 » LeetCode » 正文

1360:奇怪的电梯(lift)

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 4790     通过数: 2047

【题目描述】

大楼的每一层楼都可以停电梯,而且第i层楼(1≤i≤N)(1≤i≤N) 上有一个数字Ki(0≤=Ki≤=N)Ki(0≤=Ki≤=N) 。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:3 3 1 2 5代表了Ki(K1=3,K2=3,……)Ki(K1=3,K2=3,……) ,从一楼开始。在一楼,按“上”可以到44 楼,按“下”是不起作用的,因为没有−2−2 楼。那么,从AA 楼到BB 楼至少要按几次按钮呢?

【输入】

共有二行,第一行为三个用空格隔开的正整数,表示N,A,B(1≤N≤200,1≤A,B≤N)N,A,B(1≤N≤200,1≤A,B≤N) ,第二行为NN 个用空格隔开的正整数,表示KiKi 。

【输出】

一行,即最少按键次数,若无法到达,则输出−1−1 。

【输入样例】

5 1 5
3 3 1 2 5

【输出样例】

3

【来源】

No

 

 

 

 

 

#include <bits/stdc++.h>
#define MAXN 305
using namespace std;
struct node
{
    int x;
    int step;
    node()
    {
        x=0,step=0;
    }
};
queue<node> que;
int arr[MAXN];
int vis[MAXN];
int n,a,b;


void bfs(int x)
{
    node p,q,n1,n2;
    p.x=x;
    vis[x]=1;
    p.step=0;
    que.push(p);
    bool flag=false;

    while(!que.empty())
    {
        q=que.front();
        que.pop();
        int xx=q.x;
        if(xx==b)
        {
            flag=true;
            cout<<q.step<<endl;
            break;
        }
        n1.x=xx+arr[xx];
        n1.step=q.step+1;
        n2.x=xx-arr[xx];
        n2.step=q.step+1;

        if(n1.x>=1&&n1.x<=b&&!vis[n1.x])
        {
            que.push(n1),vis[n1.x]=1;
        }
            

        if(n2.x>=1&&n2.x<=b&&!vis[n2.x])
        {
            que.push(n2),vis[n2.x]=1;
        }
            
    }
    if(!flag)
        cout<<"-1"<<endl;
    return ;
}

int main()
{
    int i;
    cin>>n>>a>>b;
    for(i=1; i<=n; i++)
        cin>>arr[i];
    bfs(a);
    return 0;
}

 

标签:

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《一本通1360 奇怪的电梯》 发布于2020-02-25

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录