题目链接

https://www.luogu.com.cn/problem/P1135
（来自洛谷）

题目大意

n层电梯（1<=n<=200），每个电梯有个k值，代表乘坐此电梯可以到达n+k层和n-k层，当然，这必须要保证n+k层和n-k层存在，不存在是无法到达的。问最少摁多少次电梯按钮能从指定电梯到指定电梯。

解题思路

bfs，显而易见。（学长讲题的时候说是板子，我没做出来，好烦！）
但是自己写的时候并没有想到如何更新cnt的值（cnt用于记录是摁了第几次按钮），因为bfs的时候并不知道哪个是根，哪个是延伸出来的子节点，所以最后只过了50的数据。
正解是建立一个cnt数组，cnt[i]表示第i层的电梯是第几次摁的，cnt[i]值的刷新是i的父亲电梯的cnt值+1得到的。因此，只要碰到目标电梯，直接输出并return即可。
（确实挺板子的，但是实在没想出来cnt变化该怎么存储，哎菜鸡叹息）
其实，本质考察的就是图，有向图。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int a,b,n;
int vis[N];//一定别忘了标记已访问过的电梯！！！
vector<int> v[N];//存路径
int cnt[N];
void bfs(int x){
    queue<int> q;
    q.push(x);
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        for(int i=0;i<v[tmp].size();i++){
            int next=v[tmp][i];
            if(vis[next]) continue;
            vis[next]=1;
            cnt[next]=cnt[tmp]+1;//与板子题，只差这一句
            q.push(next);
            if(next==b) {cout<<cnt[next]<<endl;return ;}
        }        
    }
    cout<<-1<<endl;
    return ;    
}
int main(){
    int k;
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++){
        cin>>k;
        if(i-k>0) v[i].push_back(i-k);//要是第i个电梯能向下走k层，那么可以从i到i-k层，存下有向边
        if(i+k<=n) v[i].push_back(i+k);//要是第i个电梯能向上走k层，那么可以从i到i+k层，存下有向边
    }
    if(a==b){cout<<0<<endl;return 0;}//一定要特判一下（按我这方法的话），这个特判我也没想到（差一组样例，懒得debug了，直接下载的数据，其实这样做是不利于进步的！不建议模仿QAQ）

    vis[a]=1;//勿忘
    bfs(a);
}