# APCS實作題2022年10月第3題：石窟探險

> 日期：2024年8月6日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=j124)

## 題目

### 問題描述

有一組探險隊要去一個樹狀結構的石窟內探險，該石窟內有 $n$ 個石室，第 $i$ 個石室有一個編號 $a_i$，若 $a_i$ 為偶數則會有 $2$ 條分支(左分支和右分支)，若 $a_i$ 為奇數則有 $3$ 條分支(左分支、中分支和右分支)。

探險隊想要紀錄這個石窟的結構，每次只要第一次走到一個新的石室，就會將該石室的編號記錄在紙上，並由左到右依序走訪該石室的分支們，若走到一條死路則會在紙上紀錄一個數字 $0$，若該石室已經走完所有分支則退回到上一個石室，走訪完整個石窟後在紙上得到上一個數字序列。

探險隊回到基地後忘記計算了這個石窟內所有相鄰的石室編號相差取絕對值的總和，請幫助探險隊從紙上的序列推算出該數值。
<br />

### 輸入說明

輸入一個整數個數不超過 $10^6$ 的整數序列，石室的編號不超過 $10^5$，並保證造出來的樹深度不超過 $40$。

子題配分
- 20%：石室數量最多不超過 $20$ 個，編號均為偶數
- 20%：石室數量最多不超過 $10^3$ 個
- 60%：石室最大深度不超過 $40$ 層，而且編號和石室編號不超過 $10^5$，答案可能會超過 $2^{31}$
。
<br />

### 輸出格式

輸出一個整數代表這個石窟內所有相鄰的石室編號相差取絕對值的總和，答案大小有可能會超過 $2^{31}$。
<br />

### 範例輸入1

2 6 0 8 14 0 0 0 10 0 4 0 0

### 範例輸出1

26

<br />

<img style="display: block; margin-left: auto; margin-right: auto" height="50%" width="50%" src="https://imgur.com/4pCHgo9.png">
<div style="text-align:center">輸入範例1圖示，紅色箭頭為走訪順序。</div>
<br /><br />

### 範例輸入2

5 2 10 0 0 0 8 0 0 17 0 0 0

### 範例輸出2

26

<br />

<img style="display: block; margin-left: auto; margin-right: auto" height="50%" width="50%" src="https://imgur.com/P9RsXPN.png">
<div style="text-align:center">輸入範例2圖示，紅色箭頭為走訪順序。</div>
<br /><br />

## Python 程式碼

採用 C++ 寫法2的邏輯。費時最久約為 0.2 s，使用記憶體最多約為 18.2 MB，通過測試。

ans = 0  # 答案
head = 0  # 讀取資料用的索引值
data = list(map(int, input().split()))  # 石室資料

def dfs(pre=100001):  # 輸入前一個節點 pre，預設值為超出題目編號範圍的 100001
    global ans, head
    cur = data[head]  # 讀取現在的節點 cur
    head += 1  # 索引值加 1
    #print("pre: {:d}   cur: {:d}".format(pre, cur))  # 除錯用
    if cur == 0: return  # 遞迴出口
    if pre != 100001: ans += abs(pre - cur)  # 如果 pre 不是預設值，更新答案
    if cur&1:  # 如果 cur 是奇數，可能有 3 個子節點
        dfs(cur); dfs(cur); dfs(cur)  # 遞迴 3 次
    else:  # 如果 cur 是偶數，可能有 2 個子節點
        dfs(cur); dfs(cur)  # 遞迴 2 次

dfs()  # 呼叫 dfs
print(ans)  # 印出答案

<br /><br />

## C++ 程式碼

### 寫法1，先建立整棵樹再計算答案

由於要儲存整棵樹的資料，會使用較多的記憶體。費時最久約為 0.1 s，使用記憶體最多約為 10 MB，通過測試。

#include <iostream>
#include <vector>
#include <map>
#include <stdlib.h>  // for labs
typedef unsigned long long LL;  // 簡化名稱為 LL
using namespace std;

map<LL, vector<LL>> tree;  // 用 map 儲存地圖
LL ans = 0;  // 答案

/* 自訂函式，建立地圖 */
void build(LL pre) {  // 輸入前一個節點 pre
    LL cur; cin >> cur;  // 讀取現在的節點 cur
    //cout << "pre: " << pre << "   cur: " << cur << "\n";  // 除錯用
    if (cur == 0) return;  // 遞迴出口
    tree[pre].push_back(cur);  // 將 cur 加入 pre 的子節點之中
    if (cur&1) {  // 如果 cur 是奇數，可能有 3 個子節點
        build(cur); build(cur); build(cur);  // 遞迴 3 次
    } else {  // 如果 cur 是偶數，可能有 2 個子節點
        build(cur); build(cur);  // 遞迴 2 次
    }
}

/* 自訂函式，計算答案 */
void solve(LL pre) {  // 輸入前一個節點 pre
    //cout << "pre: " << pre << "   ans: " << ans << "\n";  // 除錯用
    vector<LL> child = tree[pre];  // 取出儲存 pre 子節點的陣列
    for(auto c : child) {  // 依序取出子節點
        ans += labs(pre - c);  // 計算答案
        solve(c);  // 遞迴，找 c 的下一層
    }
}

/* 自訂函式，印出地圖，提交程式碼測試時可省略 */
void myprint(map<LL, vector<LL>> t) {
    for(auto it = t.begin(); it != t.end(); it++) {
        cout << (*it).first << ": ";  // 印出父節點
        for(auto a : (*it).second) cout << a << " ";  // 印出子節點
        cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    build(100001);  // 呼叫 build，先代入超出題目編號範圍的 100001
    //myprint(tree);  // 印出地圖
    solve(100001);  // 呼叫 solve，先代入超出題目編號範圍的 100001，會多算 100001-tree[100001][0]
    cout << ans-(100001-tree[100001][0]) << "\n";  // 印出答案
    return 0;
}

<br /><br />

### 寫法2，不建立樹，直接計算答案

由於這個題目只要計算相鄰石室編號差的絕對值加總，不需要儲存整個地圖，可以在呼叫 dfs 遞迴時直接計算答案，花費的時間、使用的記憶體會比寫法1少很多。費時最久約為 32 ms，使用記憶體最多約為 344 kB，通過測試。

#include <iostream>
#include <stdlib.h>  // for labs
typedef unsigned long long LL;  // 簡化名稱為 LL
using namespace std;

LL ans = 0;  // 答案

void dfs(LL pre = 100001) {  // 輸入前一個節點 pre，預設值為超出題目編號範圍的 100001
    LL cur; cin >> cur;  // 讀取現在的節點 cur
    //cout << "pre: " << pre << "   cur: " << cur << "\n";  // 除錯用
    if (cur == 0) return;  // 遞迴出口
    if (pre != 100001) ans += labs(pre - cur);  // 如果 pre 不是預設值，更新答案
    if (cur&1) {  // 如果 cur 是奇數，可能有 3 個子節點
        dfs(cur); dfs(cur); dfs(cur);  // 遞迴 3 次
    } else {  // 如果 cur 是偶數，可能有 2 個子節點
        dfs(cur); dfs(cur);  // 遞迴 2 次
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    dfs();  // 呼叫 dfs
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`