蓝桥杯刷题训练(洛谷搜索官方题单)

前几天我带大家练习了搜索算法的入门题目，今天我们来看一道洛谷上面稍微有点小难度的题目。实际上搜索算法题的难度全在读懂题目上，读懂题目之后，我们很容易地可以判断出是使用BFS还是DFS，然后套模板即可。好的，废话不多说，我们拿题来看。

教算法的小程同学

290人浏览 · 2025-03-14 16:35:20

教算法的小程同学 · 2025-03-14 16:35:20 发布

前言

题目描述

呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 i 层楼（1≤i≤N）上有一个数字 Ki（0≤Ki≤N）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： 3,3,1,2,5 代表了 Ki（K1=3，K2=3，……），从 1 楼开始。在 1 楼，按“上”可以到 4 楼，按“下”是不起作用的，因为没有 −2 楼。那么，从 A 楼到 B 楼至少要按几次按钮呢？

输入格式

共二行。

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

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

输出格式

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

输入输出样例

输入 #1

5 1 5

3 3 1 2 5

输出 #1

说明/提示

对于 100% 的数据，1≤N≤200，1≤A,B≤N，0≤Ki≤N。

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

题目思考

题目要求求出最少要按几次按钮，我们很容易想到使用BFS，但是BFS的思考难度明显要比DFS大一些，所以我首先尝试使用DFS深度搜索求解了一下，注意因为时间限制，DFS解法只能在洛谷上面过6个测试点，因此DFS解法我就不多讲，附代码如下。

DFS解法

#include <iostream>
#include <cstring>
using namespace std;

const int N = 210;
int n, a, b;
int K[N];  // 记录每一层楼上的数字
bool visited[N];  // 记录是否访问过该楼层
int ans = -1;  // 初始化最小按键次数为 -1，表示无法到达

// 深度优先搜索函数
void dfs(int floor, int steps) {
    // 如果当前楼层超出范围或者已经访问过，直接返回
    if (floor < 1 || floor > n || visited[floor]) return;
    // 标记当前楼层为已访问
    visited[floor] = true;

    // 如果到达目标楼层
    if (floor == b) {
        // 如果是第一次到达目标楼层或者当前步数更少，更新最小按键次数
        if (ans == -1 || steps < ans) {
            ans = steps;
        }
        // 回溯，标记当前楼层为未访问
        visited[floor] = false;
        return;
    }

    // 尝试向上移动
    int up = floor + K[floor - 1];
    dfs(up, steps + 1);

    // 尝试向下移动
    int down = floor - K[floor - 1];
    dfs(down, steps + 1);

    // 回溯，标记当前楼层为未访问
    visited[floor] = false;
}

int main() {
    cin >> n >> a >> b;
    for (int i = 0; i < n; i++) {
        cin >> K[i];
    }

    // 初始化访问标记数组
    memset(visited, false, sizeof(visited));
    // 从起始楼层开始深度优先搜索，初始步数为 0
    dfs(a, 0);

    // 输出最小按键次数
    cout << ans << endl;

    return 0;
}

BFS解法(标准解法)

BFS队列入队出队示意图(手搓不易，给个关注吧)

BFS代码 (附详细注释)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>  
using namespace std;

// 定义最大楼层数
const int N = 210;
// 定义一个整数对类型，用于存储楼层和步数
typedef pair<int, int> PII;
// f数组用于存储每个楼层的按键值，即按该楼层的按钮后能上升或下降的层数
int f[N];  
// way数组用于标记某个楼层是否已经到达过，避免重复访问
int way[N];  
// n表示总楼层数，a表示起始楼层，b表示目标楼层
int n, a, b;

// 广度优先搜索函数，用于计算从起始楼层a到目标楼层b所需的最少步数
// a: 起始楼层
// b: 目标楼层
// step: 初始步数
int bfs(int a, int b, int step) {
    // 定义一个队列，队列中的元素是PII类型，存储楼层和到达该楼层所需的步数
    queue<PII> q;
    // 将起始楼层和初始步数加入队列
    q.push({a, step});
    // 标记起始楼层已经到达过
    way[a] = 1;  

    // 当队列不为空时，继续搜索
    while (!q.empty()) {
        // 取出队列的队首元素
        PII current = q.front();
        // 将队首元素出队
        q.pop();
        // 如果当前楼层等于目标楼层，返回到达该楼层所需的步数
        if (current.first == b) {
            return current.second;
        }
        // 计算按当前楼层按钮上升后的楼层
        int x = current.first + f[current.first];
        // 判断上升后的楼层是否在有效范围内（大于0且小于等于总楼层数），并且该楼层还未到达过
        if (x > 0 && x <= n && way[x] == 0) {
            // 标记该楼层已经到达过
            way[x] = 1;
            // 将该楼层和到达该楼层所需的步数加1后加入队列
            q.push({x, current.second+1});
        }
        // 计算按当前楼层按钮下降后的楼层
        int y = current.first - f[current.first];
        // 判断下降后的楼层是否在有效范围内（大于0且小于等于总楼层数），并且该楼层还未到达过
        if (y > 0 && y <= n && way[y] == 0) {
            // 标记该楼层已经到达过
            way[y] = 1;
            // 将该楼层和到达该楼层所需的步数加1后加入队列
            q.push({y, current.second+1});
        }
    }
    // 如果无法到达目标楼层，返回 -1
    return -1;
}

int main() {
    // 输入总楼层数n、起始楼层a和目标楼层b
    cin >> n >> a >> b;
    // 循环输入每个楼层的按键值
    for (int i = 1; i <= n; i++) {
        cin >> f[i];
    }
    // 调用bfs函数计算从起始楼层到目标楼层所需的最少步数，并输出结果
    printf("%d", bfs(a, b, 0));
    return 0;
}