【题目来源】
洛谷：P1135 奇怪的电梯 - 洛谷
【题目描述】
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 层楼 \((1\le i\le N)\) 上有一个数字 \(K_i(0\le K_i\le N)\)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如\(3,3,1,2,5\) 代表了 \(K_i(K_1=3,K_2=3,\dots)\)，从 \(1\) 楼开始。在 \(1\) 楼，按“上”可以到 \(4\) 楼，按“下”是不起作用的，因为没有 \(−2\) 楼。那么，从 A 楼到 B 楼至少要按几次按钮呢？
【输入】
共二行。
第一行为三个用空格隔开的正整数，表示 \(N,A,B(1\le N\le 200,1\le A,B\le N)\)。
第二行为 \(N\) 个用空格隔开的非负整数，表示 \(K_i\)。
【输出】
一行，即最少按键次数，若无法到达，则输出 -1。
【输入样例】
5 1 5
3 3 1 2 5
【输出样例】
3
【解题思路】
【算法标签】
《洛谷 P1135 奇怪的电梯》 #模拟# #广度优先搜索,BFS# #深度优先搜索,DFS#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 全局变量：
// n: 楼层总数
// a: 起始楼层
// b: 目标楼层
// tmp: 临时变量，用于输入
int n, a, b, tmp;// 楼层结构体：
// up: 可以向上到达的楼层
// down: 可以向下到达的楼层
// visit: 到达该楼层的最少按键次数（-1表示未访问）
struct node
{int up, down, visit;
} f[205];int main()
{// 输入楼层总数、起始楼层和目标楼层cin >> n >> a >> b;// 初始化每个楼层的信息for (int i = 1; i <= n; i++){cin >> tmp; // 输入电梯在该楼层可以移动的层数f[i].up = i + tmp; // 计算向上可达楼层f[i].down = i - tmp; // 计算向下可达楼层f[i].visit = -1; // 初始化为未访问状态}// 创建队列用于BFSqueue<node> q;// 设置起始楼层信息并加入队列f[a].visit = 0; // 起始楼层按键次数为0node tp = {f[a].up, f[a].down, f[a].visit};q.push(tp);// BFS遍历所有可能的移动while (!q.empty()){tp = q.front();q.pop();// 处理向上移动的情况if (tp.up >= 1 && tp.up <= n && f[tp.up].visit == -1){f[tp.up].visit = tp.visit + 1; // 更新按键次数node t = {f[tp.up].up, f[tp.up].down, f[tp.up].visit};q.push(t);}// 处理向下移动的情况if (tp.down >= 1 && tp.down <= n && f[tp.down].visit == -1){f[tp.down].visit = tp.visit + 1; // 更新按键次数node t = {f[tp.down].up, f[tp.down].down, f[tp.down].visit};q.push(t);}// 如果到达目标楼层，提前终止搜索if (tp.up == b || tp.down == b){break;}}// 输出到达目标楼层的最少按键次数cout << f[b].visit << endl;return 0;
}
【运行结果】
5 1 5
3 3 1 2 5
3