奇怪的电梯｜MGblog

题目：奇怪的电梯

题目描述：
假设一栋大楼有一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 i 层楼（1 \leq i \leq N）上有一个数字 K_i（0 \leq K_i \leq N）。电梯只有四个按钮：开、关、上、下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如，楼层信息为 3\ 3\ 1\ 2\ 5，代表了 K_1=3，K_2=3，K_3=1，K_4=2，K_5=5，在一楼时按“上”可以到四楼，按“下”不起作用，因为没有负楼层。求从 A 楼到 B 楼最少按几次按钮。

输入描述：

第 1 行：三个正整数，表示 N, A, B，1 \leq N \leq 200，1 \leq A, B \leq N。
第 2 行：N 个正整数，表示 K_i（每层楼的数字）。

输出描述：
一行，共一个数，表示最少按键次数。若无法到达，则输出 -1。

样例输入：

5 1 5
3 3 1 2 5

样例输出：

题意：
在第 i 层时，电梯可以上下 K_i 层。如果无法到达目标楼层，则输出 -1。

思路：广搜求最小步数（BFS）

使用 BFS 算法求解。
从起点楼层开始，将其入队并标记为已访问。
每次循环从队头取出当前楼层，检查是否能到达目标楼层。
对于当前楼层，尝试按下按钮“上”或“下”，将新楼层加入队列，标记已访问，并更新步数。
若找到目标楼层，输出步数；否则，在队列为空时输出 -1 表示无解。

AC代码：

#include<bits/stdc++.h>
#define N 1001
using namespace std;
int n, A, B, a[N], cnt, vis[N], step[N];
bool flag2 = false;
queue<int> q;

void bfs(int x) {
    q.push(x);
    while (!q.empty()) {
        int xx = q.front();
        q.pop();
        if (xx == B) {
            flag2 = true;
            break;
        }
        if (xx + a[xx] <= n && !vis[xx + a[xx]]) {
            q.push(xx + a[xx]);
            vis[xx + a[xx]] = 1;
            step[xx + a[xx]] = step[xx] + 1;
        }
        if (xx - a[xx] > 0 && !vis[xx - a[xx]]) {
            q.push(xx - a[xx]);
            vis[xx - a[xx]] = 1;
            step[xx - a[xx]] = step[xx] + 1;
        }
    }
}

int main() {
    cin >> n >> A >> B;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vis[A] = 1;
    bfs(A);
    if (flag2) {
        cout << step[B];
    } else {
        cout << -1;
    }
    return 0;
}

时间复杂度: O(N)
空间复杂度: O(N)

奇怪的电梯

题目：奇怪的电梯

热门文章