题目描述

呵呵#xff0c;有一天我做了一个梦#xff0c;梦见了一种很奇怪的电梯。

大楼的每一层楼都可以停电梯…链接直达P1135

计算机科学教育新生态

呵呵有一天我做了一个梦梦见了一种很奇怪的电梯。

大楼的每一层楼都可以停电梯而且第

\le

0≤Ki​≤N。

电梯只有四个按钮开关上下。

上下的层数等于当前楼层上的那个数字。

当然如果不能满足要求相应的按钮就会失灵。

例如

3,3,1,2,5

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

BFS思路:

首先通过输入获取数组长度N起始位置A和目标位置B。

通过输入获取数组K的值K用于存储每个位置的移动范围。

使用队列q进行广度优先搜索初始时将起始位置A入队并标记为已访问。

当队列不为空时进行循环每次从队列中取出一个位置并判断是否等于目标位置B如果是则更新ans为当前步数并结束搜索。

如果不是则判断当前位置加上K的值和减去K的值是否在有效范围内且未被访问如果是则将新位置入队并标记为已访问。

最后根据ans的值输出结果如果ans等于INT_MAX则输出-1表示无解。

注意:

wa76先判断新的下标是否合法不然容易查看vis数组会数组越界

AC100

ios::sync_with_stdio(false),cin.tie(nullptr)

using

定义全局变量ans用于存储从A到B的最小步数初始值设为INT_MAX表示未找到路径

int

初始化数组K和visK用于存储每个位置的移动范围vis用于标记位置是否已被访问vectorint

K(N

如果当前位置等于目标位置B则更新ans为当前步数并结束搜索if

(tx

如果当前位置加上K的值在有效范围内且未被访问则将新位置入队并标记为已访问if

(tx

如果当前位置减去K的值在有效范围内且未被访问则将新位置入队并标记为已访问if

(tx

根据ans的值输出结果如果ans等于INT_MAX则输出-1表示无解if

(ans