迷宮探訪 題解｜APCS 2022 年 10 月中高級 第 3 題

前置知識

這題的核心（紀錄是怎麼寫出來的、怎麼照同樣的順序讀回來）下面會從頭講；要先會的是這幾件事，同一個主題兩邊都有的，對照著讀會更快上手：

• 遞迴：NTUCPC Guide〈遞迴〉——要帶走的是「函式呼叫自己，每一層有自己的變數，做完回到上一層被呼叫的那一行接著做」；吳邦一《AP325》第 1 章 1.2「實作遞迴定義」的例題 P-1-1 合成函數（1） 是同一種「邊讀輸入邊遞迴」的寫法（教材 PDF 第 29～30 頁；Python 版第 1 章）。
• 樹（根、子節點、子樹）：NTUCPC Guide〈樹〉——這題的迷宮就是一棵樹：起點是根，每個出口通往一棵子樹。
• 堆疊（只有最後的「另一種做法」會用到）：NTUCPC Guide〈Stack／Queue／Deque〉。

簡潔題意

一座樹狀迷宮：偶數編號的石室有 \(2\) 個出口、奇數編號的有 \(3\) 個，每個出口要嘛通往下一層的一間石室、要嘛是死路。小明從起點出發，到每一間石室先記下編號，再依序走它的每個出口：死路就記一個 \(0\)；通往石室就先把那間底下的全部探訪完、回來再看下一個出口。給你這份紀錄，求所有「相連的兩間石室」編號差的絕對值總和（石室不超過 \(10^5\) 間、編號是不超過 \(10^5\) 的相異正整數、最深 \(40\) 層；答案可能超過 \(2^{31}\)）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(20\) 分）：\(n \le 20\)，編號都是正偶數，起點的所有出口都通往石室、其他石室最多一個出口通往石室。
• 子題組 2（\(20\) 分）：\(n \le 10^3\)。
• 子題組 3（\(60\) 分）：無額外限制。

紀錄是「先自己、再逐個出口」寫出來的，就照同樣的順序讀回來

小明的走法是固定的：進到石室 \(u\) 先記 \(u\)，然後第 1 個出口、第 2 個出口（奇數編號還有第 3 個），每個出口要嘛記一個 \(0\)、要嘛記下「那棵子樹的整份紀錄」。所以紀錄裡 \(u\) 後面緊接著的，就是 \(u\) 的第 1 個出口（一個數：\(0\) 或某間石室 \(v\) 的編號）；如果是 \(v\)，那 \(v\) 後面又緊接著 \(v\) 的出口……要等 \(v\) 底下整棵的紀錄全部結束，下一個數才是 \(u\) 的第 2 個出口。

關鍵在於每間石室有幾個出口，看編號的奇偶就知道，所以讀的人永遠知道「現在這個數是誰的出口」，同一份紀錄不會有第二種讀法（圖 1）。

寫成遞迴 walk(u)：\(u\) 的編號已經讀過了，接著從紀錄讀 \(u\) 的每一個出口；讀到 \(0\) 就跳過，讀到 \(v\) 就把 \(|u - v|\) 加進答案，再呼叫 walk(v) 把 \(v\) 底下整棵讀完——回來的時候，讀取位置剛好停在 \(u\) 的下一個出口。整份紀錄只有一行、長度不固定，先用 while (cin >> x) 全部讀進陣列，再用一個全域的 cursor 記「下一個還沒讀的位置」。

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100000;
int record[3 * MAX_N + 5];        // 整份紀錄：石室編號與 0，最多 3n + 1 個數
int total = 0;                    // 紀錄裡有幾個數
int cursor = 0;                   // 下一個還沒讀的位置

long long walk(int u) {           // u 的編號已經讀過了，接著讀它的每一個出口
    int exits = (u % 2 == 0) ? 2 : 3;
    long long sum = 0;
    for (int k = 0; k < exits; k++) {
        int v = record[cursor];       // 這個出口通往哪一間：0 = 死路
        cursor++;
        if (v == 0) continue;
        sum += abs(u - v);            // u 與 v 相連
        sum += walk(v);               // 把 v 底下整棵走完，cursor 會停在 v 的下一個出口
    }
    return sum;
}

int main() {
    int x;
    while (cin >> x) {
        record[total] = x;
        total++;
    }
    cursor = 1;                       // record[0] 是起點，已經「讀過」了
    cout << walk(record[0]) << endl;
    return 0;
}

每個數只會被讀一次，\(O(n)\)。遞迴的深度就是迷宮的層數，題目保證不超過 \(40\)。答案最多 \((n - 1) \times 10^5 \approx 10^{10}\)，超過 int，答案與 walk 的回傳值都用 long long（2.9）。紀錄的長度：\(n\) 間石室最多 \(3n\) 個出口，其中 \(n - 1\) 個通往石室、其餘是 \(0\)，所以整份紀錄不超過 \(3n + 1\) 個數，陣列開 3 * MAX_N + 5 就夠。

三個子題組用的是同一份程式：子題組 1 的「全部偶數、其他石室最多一個出口」只是讓樹長成起點底下的兩條鏈，沒有比較簡單的讀法，直接寫滿分解，\(100\) 分穩穩到手。

測過再交：範例的答案都很小

兩個範例都有「中間的出口是死路、兩邊的出口通往石室」這種情況，沒蓋到的是：只有起點一間、起點的出口全是死路、起點的第 1 個出口是死路而第 2 個才通往石室，以及編號差很大、答案超過 int 的大迷宮。

五筆都親眼看過正確，這題就穩了。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int root;
    cin >> root;
    stack<pair<int, int>> path;       // (石室編號, 還剩幾個出口沒看)：從起點到目前所在石室的路
    path.push({root, (root % 2 == 0) ? 2 : 3});
    long long sum = 0;
    int v;
    while (cin >> v) {
        int u = path.top().first;     // 目前所在的石室，v 是它的下一個出口
        path.top().second--;
        if (v != 0) {
            sum += abs(u - v);
            path.push({v, (v % 2 == 0) ? 2 : 3});
        }
        while (!path.empty() && path.top().second == 0) path.pop();   // 出口都看完了，退回上一間
    }
    cout << sum << endl;
    return 0;
}