一、题目

在这里插入图片描述

二、解题思路

看到该题，我第一反应是使用动态规划进行求解，但是在分析题目的时候发现，该电梯不同于生活中的电梯：想去几层就去几层，而是去的地方是固定的。那么很容易想到，整个电梯的运行情况实际上可以看做是一张图，因此，该题的求解应该与图有关，而不是动态规划。
题目要求计算A楼到B楼最少要按几次按钮（实际上是需要中转几次。不考虑按开和关按钮）。当构建好图时，该问题可以转化为B的几阶邻居是A，很容易想到使用层次遍历法进行问题的求解。
有两处细节需要注意：（1）在构建图时，我们构建的是有向图，而非无向图。因为A可以到达B时，不代表B可以到达A，比如题目中1可以到达5，但是5无法到达1。（2）当A==B时，最少按键次数为0。

三、代码

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int N, A, B;

//进行层次遍历，根节点为B
int bfs(vector<vector<int>> &adj){
    if(A==B)return 0;
    vector<int> visit(N+1, 0);
    queue<int> node, layer;
    node.push(B);
    visit[B]=1;
    layer.push(0);
    while(!node.empty()){
        int now_node=node.front(), now_layer=layer.front();
        node.pop();
        layer.pop();
        for(int i=0;i<adj[now_node].size();i++){
            int next=adj[now_node][i];
            if(next==A)return now_layer+1;
            if(!visit[next]){
                node.push(next);
                layer.push(now_layer+1);
                visit[next]=1;
            }
        }
    }
    return -1;
}

int main(){
    cin>>N>>A>>B;
    vector<vector<int>> adj(N+1, vector<int>());
    //构建邻接表
    for(int i=1;i<=N;i++){
        int Ki;
        cin>>Ki;
        if(i-Ki>0){
            adj[i-Ki].push_back(i);
        }
        if(i+Ki<=N){
            adj[i+Ki].push_back(i);
        }
    }
    int ret=bfs(adj);
    cout<<ret;
}