1.6.2 奇怪的电梯(BFS)

举报
irrational 发表于 2022/01/17 23:28:27 2022/01/17
1.1k+ 0 0
【摘要】 Description 有一天uncle-lu做了一个梦,梦见了一种很奇怪的电梯。 大楼的每一层楼都可以停电梯,而且i层楼上有一个数字。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。 当然,如果不能满足要求,相应的按钮就会失灵。例如:3,3,1,2,5代表了,从1楼开始。在1楼,按“上”可以到4楼,按“...

Description

有一天uncle-lu做了一个梦,梦见了一种很奇怪的电梯。
大楼的每一层楼都可以停电梯,而且i层楼上有一个数字。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。
当然,如果不能满足要求,相应的按钮就会失灵。例如:3,3,1,2,5代表了,从1楼开始。在1楼,按“上”可以到4楼,按“下”是不起作用的,因为没有−2楼。
那么,从A楼到B楼至少要按几次按钮呢?

Input

第一行为333个用空格隔开的正整数,表示N,A,B

第二行为N个用空格隔开的非负整数,表示Ki。

Output

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

Sample Input 1

5 1 5
3 3 1 2 5

Sample Output 1

3

Hint

1≤N≤200,1≤A,B≤N


      #include <cstring>
      #include <iostream>
      #include <algorithm>
      #include <queue>
      using namespace std;
      int h[210];
      typedef pair<int, int> PII;
      const int N = 2000000;
      int n,a,b;
      int d[N];
      inline int bfs()
      {
          queue<int> q;
         memset(d, -1, sizeof d);
          d[a] = 0;
          q.push(a);
         while (q.size())
          {
             auto t = q.front();
             //cout<<t<<endl;
              q.pop();
             for (int i = 0; i <= 1; i ++ )
              {
                 int y;
                 if(i) y=t+h[t];
                 else  y=t-h[t];
                 if (y<=0||y>b)continue;
                 if (d[y] == -1)
                  {
                      d[y] = d[t] + 1;
                      q.push(y);
                  }
              }
          }
         return d[b];
      }
      int main()
      {
          cin >> n >> a >> b;
         for (int i = 1; i <= n; i ++ )
             scanf("%d", &h[i]);
          cout << bfs() << endl;
         return 0;
      }
  
 

      #include<cstdio>
      int n,st,ed,p=0;
      int step[210],lift[210];
      bool pd=true;
      int main()
      {
         scanf("%d %d %d",&n,&st,&ed);
         for(int i=1;i<=n;i++)
          {
              step[i]=-1;
             scanf("%d",&lift[i]);
          }
          step[st]=0;
         while(step[ed]==-1 && pd)
          {
              pd=false;
             for(int i=1;i<=n;i++)
                 if(step[i]==p)
                  {
                     int j=i+lift[i];
                     if(j<=n && step[j]==-1)
                      {
                          step[j]=p+1;
                          pd=true;
                      }
                      j=i-lift[i];
                     if(j>0 && step[j]==-1)
                      {
                          step[j]=p+1;
                          pd=true;
                      }
                  }
              p++;
          }
         printf("%d",step[ed]);
         return 0;
      }
  
 

两种方法都可以

文章来源: blog.csdn.net,作者:irrationality,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/weixin_54227557/article/details/120606159

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

作者其他文章

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

    全部回复

    上滑加载中

    设置昵称

    在此一键设置昵称,即可参与社区互动!

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。