1.6.2 奇怪的电梯(BFS)

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