P1135 奇怪的电梯

yhx0322 · 2023-11-22 21:37:43 · 题解

Description

题目传送门

Solution

这道题可以用 DFS，同样也可以用 BFS。

下面给出 BFS 求最短路的思路：

• 首先判断特殊情况：起点等于终点，直接输出 0。
• 将起始点放入队列 q 中。注意这里使用的是手动模拟队列，而不是 STL 中的 queue。
• 因为要处理方向的变换，设置方向数组 f，值分别为 1, -1。每次循环两个方向，计算新的坐标：q_h + {f}_{i} \times a_{q_h}。这里 h 代表当前头部元素的下标。
• 如果新的坐标 oi 没有被标记过，便可以入队、标记、更新最短路了。
• 如果发现 oi 正好等于终点，输出 d_{oi} 即可。这里的 d 数组代表起点到每个点的最短路。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 210;
int n,s,e,a[N],q[N],d[N],t,h;
bool f[N];
int f[3] = {0,1,-1};


int main() {
    cin >> n >> s >> e;
    for (int i = 1;i <= n;i++) cin >> a[i];
    if (s == e) {
        cout << 0;
        return 0;
    }
    t = 1,h = 1;
    q[1] = s; d[s] = 0; f[s] = true; // 起点要标记
    int oi;
    while (h <= t) {
        for (int i = 1;i <= 2;i++) {
            oi = q[h] + f[i] * a[q[h]]; // 计算新的坐标
            if (oi >= 1 && oi <= n && !f[oi]) {
                t++;
                // 入队、标记、更新最短路
                q[t] = oi;
                d[oi] = d[q[h]] + 1;
                f[oi] = true;
                if (oi == e) { // 走到终点 e
                    cout << d[oi];
                    return 0;
                }
            }
        }
        h++;
    }
    cout << -1;
    return 0;
}