P1135 奇怪的电梯题解

wangjue1629 · 2023-11-23 16:04:23 · 题解

Solution

题目传送门

题目分析

我们要计算从起始楼层 A 到目标楼层 B 的最短距离。电梯每次移动的楼层数由当前楼层的数字 k_i 决定，可以向上或向下移动。关键在于电梯的移动规则，设计一个算法来找到最短路径。如果无法到达目标楼层，返回 -1。

题目思路

这道题我一开始是用的 DFS 做的，但是后来发现 BFS 更好。

使用 BFS 是因为我们需要找到最短路径。BFS 适合于在未加权的图中寻找最短路径。从起始楼层开始，将其添加到队列中。

解题步骤

每次从队列中取出一个元素，并探索它可以直接达到的楼层（根据 k_i 向上或向下移动）。
如果某个可达的楼层是目的地，则返回到达该楼层所需的步数。如果无法到达目标楼层，返回 -1。

但是，我们还要防止重复计算，我们可以使用一个布尔数组 vis 来标记已经访问过的楼层，这样可以避免重复访问同一楼层。

AC Code

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 200 + 10;
int a[maxn];
bool vis[maxn]; //标记每层楼是否已访问
int step[maxn]; //记录到达每层楼的最小步数
//BFS 函数，计算从 st（起始楼层）到 ed（目标楼层）的最少步数
int bfs(int st, int ed, int n){
    if(st == ed) return 0; //如果起始楼层和目标楼层相同，则无需移动
    queue<int> q;
    q.push(st); //将起始楼层加入队列
    vis[st] = true; //标记起始楼层为已访问
    step[st] = 0;
    while(!q.empty()){
        int cnt = q.front();
        q.pop(); 
        //获取队列前端的楼层，并弹出这个楼层
        int up = cnt + a[cnt]; //计算向上移动的目标楼层
        int down = cnt - a[cnt]; //计算向下移动的目标楼层
        //检查向上移动是否可行
        if(up <= n && !vis[up]){
            vis[up] = true;
            step[up] = step[cnt] + 1;
            q.push(up); //将新楼层加入队列
            if(up == ed){ //如果达到目标楼层，返回步数
                return step[up];
            }
        }
        //检查向下移动是否可行
        if(down >= 1 && !vis[down]){
            vis[down] = true;
            step[down] = step[cnt] + 1;
            q.push(down); //将新楼层加入队列
            if(down == ed){ //如果达到目标楼层，返回步数
                return step[down];
            }
        }
    }
    return -1; //如果无法到达目标楼层，返回 -1
}
int main(){
    int n, st, ed;
    cin >> n >> st >> ed;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    memset(vis, false, sizeof(vis));
    int result = bfs(st, ed, n);
    cout << result << endl;
    return 0;
}

时间复杂度：O(n)，可以通过本题。

P1135 奇怪的电梯 题解