洛谷 P1135 奇怪的电梯

链接直达：P1135 奇怪的电梯 - 洛谷 | 计算机科学教育新生态

题目来源

洛谷

题目内容

奇怪的电梯

题目背景

感谢 @yummy 提供的一些数据。

题目描述

呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 $i$ 层楼（$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$，……），从 $1$ 楼开始。在 $1$ 楼，按“上”可以到 $4$ 楼，按“下”是不起作用的，因为没有 $-2$ 楼。那么，从 $A$ 楼到 $B$ 楼至少要按几次按钮呢？

输入格式

共二行。

第一行为三个用空格隔开的正整数，表示 $N,A,B$（$1\le N\le 200$，$1\le A,B\le N$）。

第二行为 $N$ 个用空格隔开的非负整数，表示 $K_i$。

输出格式

一行，即最少按键次数，若无法到达，则输出 -1。

样例 #1

样例输入 #1

5 1 5
3 3 1 2 5

样例输出 #1

3

提示

对于 $100\%$ 的数据，$1\le N\le 200$，$1\le A,B\le N$，$0\le K_i\le N$。

本题共 $16$ 个测试点，前 $15$ 个每个测试点 $6$ 分，最后一个测试点 $10$ 分。

知识点

1. BFS
2. Dijkstra

题目思路

题目提到最短路径就想到可以用BFS和迪杰斯特拉，比较快，这里只讲BFS

BFS思路:

首先，通过输入获取数组长度N，起始位置A和目标位置B。通过输入获取数组K的值，K用于存储每个位置的移动范围。
使用队列q进行广度优先搜索，初始时将起始位置A入队，并标记为已访问。当队列不为空时，进行循环，每次从队列中取出一个位置，并判断是否等于目标位置B，如果是，则更新ans为当前步数，并结束搜索。 如果不是，则判断当前位置加上K的值和减去K的值是否在有效范围内且未被访问，如果是，则将新位置入队，并标记为已访问。
最后，根据ans的值输出结果，如果ans等于INT_MAX，则输出-1表示无解。

注意:

1. 数组下标从一开始，和题意一致不容易出错，没开大数组 wa76
2. 先判断新的下标是否合法，不然容易查看vis数组会数组越界 AC100

AC代码

1. BFS版

//
// Created by Jisam on 2024/7/7.
//
#include <bits/stdc++.h>
#define PSI pair<string,int>
#define PII pair<int,int>
#define x first
#define y second
// 使用命名空间std，方便访问标准库中的函数和对象
#define code_by_jisam ios::sync_with_stdio(false),cin.tie(nullptr)
using namespace std;// 定义常量N，表示最大值为10^5+5
const int N = 1e5 + 5;// 定义全局变量ans，用于存储从A到B的最小步数，初始值设为INT_MAX表示未找到路径
int ans = INT_MAX;// 定义函数solve，用于解决从位置A到位置B的最小步数问题
void solve() {// 输入N，A，B，分别表示数组长度和起始、目标位置int N, A, B;cin >> N >> A >> B;// 初始化数组K和vis，K用于存储每个位置的移动范围，vis用于标记位置是否已被访问vector<int> K(N + 2, 0), vis(N + 2, 0);// 输入数组K的值for (int i = 1; i <= N; i++) {cin >> K[i];}// 使用队列q来进行广度优先搜索queue<PII> q;q.push({A, 0}); // 将起始位置A入队，并标记为已访问vis[A] = 1;// 当队列不为空时，进行循环while (q.size()) {// 出队并获取当前位置和步数int tx = q.front().x;int ty = q.front().y;q.pop();// 如果当前位置等于目标位置B，则更新ans为当前步数，并结束搜索if (tx == B) {ans = ty;break;}// 如果当前位置加上K的值在有效范围内且未被访问，则将新位置入队，并标记为已访问if (tx + K[tx] > 0 && tx + K[tx] <= N && !vis[tx + K[tx]]) {q.push({tx + K[tx], ty + 1});vis[tx + K[tx]] = 1;}// 如果当前位置减去K的值在有效范围内且未被访问，则将新位置入队，并标记为已访问if (tx - K[tx] > 0 && tx - K[tx] <= N && !vis[tx - K[tx]]) {q.push({tx - K[tx], ty + 1});vis[tx - K[tx]] = 1;}}// 根据ans的值输出结果，如果ans等于INT_MAX，则输出-1表示无解if (ans == INT_MAX) {cout << -1;} else {cout << ans;}
}// 主函数
int main() {code_by_jisam;// 调用solve函数解决问题solve();// 程序正常退出return 0;
}