洛谷題解——P1135：奇怪的電梯

題目相關

題目連結

洛谷，https://www.luogu.com.cn/problem/P1135。

計蒜客，https://nanti.jisuanke.com/t/T1859。

題目描述

有一天我做了一個夢，夢見了一種很奇怪的電梯。大樓的每一層樓都可以停電梯，而且第 i 層樓(1≤i≤N)上有一個數字 Ki​(0≤Ki​≤N)。電梯隻有四個按鈕：開，關，上，下。上下的層數等于目前樓層上的那個數字。當然，如果不能滿足要求，相應的按鈕就會失靈。例如：3, 3 ,1 ,2 ,5 代表了 Ki​(K1​=3, K2​=3, …)，從 1 樓開始。在 1 樓，按“上”可以到 4 樓，按“下”是不起作用的，因為沒有 −2 樓。那麼，從 A 樓到 B 樓至少要按幾次按鈕呢？

輸入格式

共二行。

第一行為 3 個用空格隔開的正整數，表示 N,A,B(1≤N≤200, 1≤A,B≤N)。

第二行為 N 個用空格隔開的非負整數，表示 Ki​。

輸出格式

一行，即最少按鍵次數,若無法到達，則輸出 −1。

輸入樣例

5 1 5
3 3 1 2 5
           

輸出樣例

3
           

題目分析

我們看到題目中有”至少“這個字眼，基本可以确定這題可是用 BFS 來解。

題意分析

就是從 A 樓出發，到達 B 樓至少需要幾次按電梯，每個樓層的電梯走幾樓是不一樣的，但是每個樓層有兩個動作：向上或者向下。

樣例資料分析

根據樣例資料，本樓一共 5 層，A=1，B=5。這 5 層裡每層動作為 3 3 1 2 5。什麼意思呢？

1、在 1 樓隻能向上 3 層或者向下 3 層。

2、在 2 樓隻能向上 3 層或者向下 3 層。

3、在 3 樓隻能向上 1 層或者向下 1 層。

4、在 4 樓隻能向上 2 層或者向下 2 層。

5、在 5 樓隻能向上 5 層或者向下 5 層。

下面我們來分析一下答案怎麼來的。

1、從 1 樓開始，我們有兩個選擇，向上 3 層或者向下 3 層。向下三層是 -2 樓，向上三層是 4 樓。由于本題沒有負數樓層，是以隻能向上。這樣到達了 4 樓，目前按了 1 次。

2、從 4 樓開始，我們有兩個選擇，向上 2 層或者向下 2 層。向下三層是 2 樓，向上三層是 6 樓。由于本題隻有 5 樓，是以隻能向下。這樣到達了 2 樓，目前按了 2 次。

3、從 2 樓開始，我們有兩個選擇，向上 3 層或者向下 3 層。向下三層是 -1 樓，向上三層是 5 樓。由于本題沒有負數樓層，是以隻能向上。這樣到達了 5 樓，目前按了 3 次。

程式設計思路

套用标準 BFS 模闆即可。

AC 參考代碼

#include <iostream>
#include <queue>

using namespace std;

const int MAXN = 200+2;

typedef struct _POS {
    int x;//樓層
    int step;//步數
} POS;

typedef struct _MAZE {
    int n;//樓層
    int a;//出發樓層
    int b;//終點樓層
    int nums[MAXN];//每層的動作
    bool vis[MAXN];
} MAZE;

MAZE maze;

int bfs(MAZE &maze) {
    POS cur = {maze.a, 0};//目前樓層
    POS next;//下一個樓層

    //推入起點
    maze.vis[cur.x]=true;
    queue<POS> q;
    q.push(cur);

    while (false==q.empty()) {
        //取出對首結點
        cur = q.front();
        q.pop();

        if (cur.x == maze.b) {
            return cur.step;
        }

        //下樓
        next.x = cur.x-maze.nums[cur.x];
        next.step = cur.step+1;
        if (next.x>0 && false==maze.vis[next.x]) {
            q.push(next);
            maze.vis[next.x] = true;
        }

        //上樓
        next.x = cur.x+maze.nums[cur.x];
        next.step = cur.step+1;
        if (next.x<=maze.n && false==maze.vis[next.x]) {
            q.push(next);
            maze.vis[next.x] = true;
        }
    }
    return -1;
}

int main() {
    cin >> maze.n >> maze.a >> maze.b;
    for (int i=1; i<=maze.n; i++) {
        cin>>maze.nums[i];
    }

    cout << bfs(maze) << endl;

    return 0;
}