题目传送门
一、广度优先搜索
#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;
}