总结与感悟
1、查找最短路径，首选广度优先搜索，深度优先搜索和动态规划都似乎有大炮打蚊子的嫌疑，不好想，细节多。
2、广度优先搜索，一般入队列的都是一个结构体或者pair<int,int> ，因为如果只是一个整数，描述的信息量太小。
3、需要有一个st数组，用来记录是否已经走过，走了几步，防止走回头路，一般喜欢初始化为-1，表示没有走过。之所以不初始化为0，是因为0可能是出发点，步数为0，这和没走过是不一样的。
4、不出界+没走过是判断条件。
5、每一步都是上一步的步数+1.
一、广度优先搜索
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n; //n层楼
int a; //从a层
int b; //到b层
int k[N];//k[i]数组,描述i层楼，可以向上+向下几层楼(如果不出界的话)
struct rule {
int floor; //当前楼层
int step; //到达此楼层需要的次数
};
int st[N];
//起点a层到i层的次数，最终结果就是st[b]。有两个作用：1、此楼层是否走过，
// 2、如果走过，第一次到达时的次数（最少次数）是多少
void bfs() {
//初始化为-1,标识没有走过
memset(st, -1, sizeof(st));
//a楼到a楼需要0步
st[a] = 0;
//任务队列q
queue<rule> q;
//将初始化结点入入队列
q.push(rule{a, 0});
//地球不爆炸，我们不放假
while (!q.empty()) {
//套路
rule p = q.front();
q.pop();
//尝试两种可能，上和下,这个-1至+1，步长为2用的好啊！
for (int i = -1; i <= 1; i += 2) {
//下一次到达的可能楼层
int nx = p.floor + k[p.floor] * i;
//如果没有出界，并且，记录过的最优解需要更新的话
if (nx >= 1 && nx <= n && st[nx] == -1) {
st[nx] = p.step + 1; //步数加1
q.push(rule{nx, p.step + 1});
}
}
}
}
int main() {
//输入
cin >> n >> a >> b;
for (int i = 1; i <= n; ++i) cin >> k[i];
//广度优先搜索
bfs();
//输出结果
printf("%d", st[b]);
return 0;
}
二、深度优先搜索
#include <bits/stdc++.h>
using namespace std;
int n; //n层楼
int a; //从a层
int b; //到b层
const int N = 100010;
const int INF = 0x3f3f3f3f;
int k[N]; //k数组表示第一层出现的数字k[i]
int st[N]; //这个楼层是不是已经到达过,防止在深度优先搜索时走回头路，那就是个死循环，这点很重要
int res = INF; //最优步数
//floor表示当前搜到的楼层,step表示已经切换过的次数
void dfs(int floor, int step) {
// 减枝，对于已经超过已知最短路径的分支，不用再继续探索，就算是后面可以成功到达b，也不可能比已知路径短。
// 不加这句，会有两个点的TLE
if (step > res) return;
//如果成功到达b楼，那么对比一下本次的步数与最优步数的大小，小的保留
//递归的出口
if (floor == b) {
res = min(res, step);
return;
}
//标识本楼层走过了
st[floor] = 1;
//上不越界就搜
int x = floor + k[floor];
if (x <= n && !st[x]) dfs(x, step + 1);
//下不越界就搜
int y = floor - k[floor];
if (y >= 1 && !st[y]) dfs(y, step + 1);
//回溯.标识本楼层未走过
st[floor] = 0;
}
int main() {
//输入
cin >> n >> a >> b;
for (int i = 1; i <= n; i++) cin >> k[i];
//标识已使用
st[a] = 1;
//深搜,从楼层a出发，已经走了0步
dfs(a, 0);
//如果所有的分支全部走完，但没有机会到达b楼层，那么,res就不会变改写，就一直是INF，依此判断是否不可达
if (res != INF) printf("%d", res);
else printf("-1");
return 0;
}
三、动态规划
#include<bits/stdc++.h>
using namespace std;
/**
动态规划，设f[i]为到第i层的按键最少次数
*/
const int N = 100010;
const int INF = 0x3f3f3f3f;
int n; //n层楼
int a; //从a层
int b; //到b层
int k[N]; //k数组表示第一层出现的数字k[i]
int f[N]; //设f[i]为到第i层的按键次数最少(这个定义非常妙，最终的结果保存在f[b]里，
// 而f[b]是通过f[i]推导出来的)
/**
*/
int main() {
//初始化为INF
memset(f, 0x3f, sizeof f);
//读入
cin >> n >> a >> b;
for (int i = 1; i <= n; i++) cin >> k[i];
//base case,边界条件
f[a] = 0;
/******这个变量+循环尝试的方法很重要啊！******/
bool isLoop = true; //是否需要继续尝试，当本次操作没有修改时，就不需要继续操作了，
// 因为这就是无法再继续更新的意思。
while (isLoop) { //用这个循环控制，是最好理解的，而不是网上说的什么n次，那个n次是玄学，非科学
isLoop = false;
for (int i = 1; i <= n; i++) { //讨论在每一层楼时的情况
int x = i - k[i]; //下楼
int y = i + k[i]; //上楼
//如果下楼的步数优于现有解，那么优化掉
if (f[x] > f[i] + 1 && x >= 1) f[x] = f[i] + 1, isLoop = true;
//如果上楼的步数优于现有解，那么优化掉
if (f[y] > f[i] + 1 && y <= n) f[y] = f[i] + 1, isLoop = true;
}
}
//还是初始值的，表示无法到达！
if (f[b] == INF) cout << -1;
else cout << f[b]; // f[b]里保存的是结果
return 0;
}