个人成立公司怎么做企业网站,登陆wordpress忘记密码,学习网站免费,微网站制作工具链接直达#xff1a;P1135 奇怪的电梯 - 洛谷 | 计算机科学教育新生态
题目来源
洛谷
题目内容
奇怪的电梯
题目背景
感谢 yummy 提供的一些数据。
题目描述
呵呵#xff0c;有一天我做了一个梦#xff0c;梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯…链接直达P1135 奇怪的电梯 - 洛谷 | 计算机科学教育新生态
题目来源
洛谷
题目内容
奇怪的电梯
题目背景
感谢 yummy 提供的一些数据。
题目描述
呵呵有一天我做了一个梦梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯而且第 i i i 层楼 1 ≤ i ≤ N 1 \le i \le N 1≤i≤N上有一个数字 K i K_i Ki 0 ≤ K i ≤ N 0 \le K_i \le N 0≤Ki≤N。电梯只有四个按钮开关上下。上下的层数等于当前楼层上的那个数字。当然如果不能满足要求相应的按钮就会失灵。例如 3 , 3 , 1 , 2 , 5 3, 3, 1, 2, 5 3,3,1,2,5 代表了 K i K_i Ki K 1 3 K_13 K13 K 2 3 K_23 K23……从 1 1 1 楼开始。在 1 1 1 楼按“上”可以到 4 4 4 楼按“下”是不起作用的因为没有 − 2 -2 −2 楼。那么从 A A A 楼到 B B B 楼至少要按几次按钮呢
输入格式
共二行。
第一行为三个用空格隔开的正整数表示 N , A , B N, A, B N,A,B 1 ≤ N ≤ 200 1 \le N \le 200 1≤N≤200 1 ≤ A , B ≤ N 1 \le A, B \le N 1≤A,B≤N。
第二行为 N N N 个用空格隔开的非负整数表示 K i K_i Ki。
输出格式
一行即最少按键次数若无法到达则输出 -1。
样例 #1
样例输入 #1
5 1 5
3 3 1 2 5样例输出 #1
3提示
对于 100 % 100 \% 100% 的数据 1 ≤ N ≤ 200 1 \le N \le 200 1≤N≤200 1 ≤ A , B ≤ N 1 \le A, B \le N 1≤A,B≤N 0 ≤ K i ≤ N 0 \le K_i \le N 0≤Ki≤N。
本题共 16 16 16 个测试点前 15 15 15 个每个测试点 6 6 6 分最后一个测试点 10 10 10 分。
知识点
BFSDijkstra
题目思路 题目提到最短路径就想到可以用BFS和迪杰斯特拉比较快这里只讲BFS BFS思路: 首先通过输入获取数组长度N起始位置A和目标位置B。通过输入获取数组K的值K用于存储每个位置的移动范围。 使用队列q进行广度优先搜索初始时将起始位置A入队并标记为已访问。当队列不为空时进行循环每次从队列中取出一个位置并判断是否等于目标位置B如果是则更新ans为当前步数并结束搜索。 如果不是则判断当前位置加上K的值和减去K的值是否在有效范围内且未被访问如果是则将新位置入队并标记为已访问。 最后根据ans的值输出结果如果ans等于INT_MAX则输出-1表示无解。 注意: 数组下标从一开始和题意一致不容易出错没开大数组 wa76先判断新的下标是否合法不然容易查看vis数组会数组越界 AC100 AC代码
BFS版
//
// Created by Jisam on 2024/7/7.
//
#include bits/stdc.h
#define PSI pairstring,int
#define PII pairint,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^55
const int N 1e5 5;// 定义全局变量ans用于存储从A到B的最小步数初始值设为INT_MAX表示未找到路径
int ans INT_MAX;// 定义函数solve用于解决从位置A到位置B的最小步数问题
void solve() {// 输入NAB分别表示数组长度和起始、目标位置int N, A, B;cin N A B;// 初始化数组K和visK用于存储每个位置的移动范围vis用于标记位置是否已被访问vectorint K(N 2, 0), vis(N 2, 0);// 输入数组K的值for (int i 1; i N; i) {cin K[i];}// 使用队列q来进行广度优先搜索queuePII 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;
}
