洛谷题目：P1135 奇怪的电梯题解

devtools/2025/1/18 19:26:41/

前言：

这道题的难度属于中等难度，做起来其实很简单的，只要掌握DFS、BFS这道题只用不超过20分钟就可以做完这道题。

#解题步骤：

另：这道题可以通过广度优先搜索（BFS）来解决。BFS是一种适合解决最短路径问题的算法。

##BFS算法步骤：

1、初始化：

创建一个队列 $q$ ，用于存储待处理的节点（楼层）。

创建一个数组 $d$ ，用于记录从起始楼层 $A$ 到每个楼层的最短距离。初始时，所有距离把它

设为-1，表示莫访问。

把起始楼层 $A$ 加入队列，并将 $dist[A]$ 设为0。

2、BFS遍历：

从队列中驱虎一个节点（当前楼层）。

计算从当前楼层可到达的上下楼层。

如果把这些楼层在范围内（1~N）且未访问过（ $dist$ 为-1），则将这些楼层假如队列，并且

更新它们的 $dist$ 值当前楼层的 $dist$ 值+1。

3、结束当前条件：

如果队列为空，表所有可到达楼层都处理完了。

如果目标楼层 $B$ 访问过（ $dist[B]$ 不为-1），则 $dist[B]$ 从A道B的最短路径长度。

如果目标楼层 $B$ 莫被访问（ $dist[B]$ 仍然为-1），表示无法从A到B，最终输出-1。

###代码

#include <bits/stdc++.h>
using namespace std;
int N, A, B;
int main() {cin >> N >> A >> B;vector<int> K(N + 1);for (int i = 1; i <= N; ++i) {cin >> K[i];}vector<int> d(N + 1, -1);  // 记录从起始楼层到每个楼层的最短距离queue<int> q;q.push(A);d[A] = 0;while (!q.empty()) {int c = q.front();q.pop();// 计算上下楼层int up = c + K[c];int dn = c - K[c];// 检查上层是否在范围内且未被访问过if (up <= N && d[up] == -1) {q.push(up);d[up] = d[c] + 1;}// 检查下层是否在范围内且未被访问过if (dn >= 1 && d[dn] == -1) {q.push(dn);d[dn] = d[c] + 1;}}// 输出结果cout << d[B] << endl;return 0;
}