AcWing 6047. 奇怪的电梯
原题链接
简单
作者:
愛_
,
2024-11-24 18:58:18
,
所有人可见
,
阅读 31
#include <bits/stdc++.h>
using namespace std;
const int N = 300;
int n, k, l;
int a[N]; // 每层楼的步长数组
int b[N]; // 用于记录每个楼层的最小按键次数
// BFS函数,返回从楼层 k 到楼层 l 最少的按键次数
int bfs(int n, int start, int target) {
queue<int> q; // BFS队列
memset(b, -1, sizeof(b)); // 初始化为-1,表示楼层未访问过
q.push(start - 1); // 从楼层 k 开始,注意转换为 0-based 索引
b[start - 1] = 0; // 起始楼层的按键次数为 0
while (!q.empty()) {
int t = q.front();
q.pop();
// 上按钮:跳到楼层 t + a[t]
int up = t + a[t];
if (up >= 0 && up < n && b[up] == -1) { // 检查新楼层是否在有效范围内
b[up] = b[t] + 1; // 更新按键次数
q.push(up); // 将新的楼层加入队列
}
// 下按钮:跳到楼层 t - a[t]
int down = t - a[t];
if (down >= 0 && down < n && b[down] == -1) { // 检查新楼层是否在有效范围内
b[down] = b[t] + 1; // 更新按键次数
q.push(down); // 将新的楼层加入队列
}
}
return b[target - 1]; // 返回目标楼层的按键次数,注意转换为 0-based 索引
}
int main() {
cin >> n >> k >> l; // 输入楼层数 n,起始楼层 k,目标楼层 l
for (int i = 0; i < n; i++) {
cin >> a[i]; // 输入每层楼的步长数组 a[]
}
int result = bfs(n, k, l);
cout << result << endl; // 输出最少按键次数,如果无法到达则为 -1
return 0;
}