迷宮探訪 (APCS 2022-10 中高級)

小明正探訪一個樹狀迷宮。這個樹狀迷宮由若干石室組成，每一間石室有一個正整數編號，偶數編號的石室有左右兩個可能通往下一層石室的出口，而奇數編號的石室則有左中右三個可能通往下一層石室的出口通道，但出口通道也可能只是死路無法通往任何其他石室。

小明由起點石室出發，依序經由左（中）右的出口通道到達下一層的石室；每到達一個石室後，他會以與起點同樣的方式遞迴探訪該石室下層的所有石室，最後回到該石室。在起點石室的出口通道皆探訪完畢後，則迷宮探訪結束。小明在探索迷宮時，對於每個石室，會在第一次進入該石室時記錄其編號，如果石室的某出口是死路時，則記錄一個零。根據小明的紀錄，請計算出迷宮中所有相連石室編號差值的絕對值總和。

例如下面這個樹狀迷宮的例子，矩形是奇數編號的石室而橢圓形是偶數編號的石室，其中 \(5\) 號石室是起點，旁邊標註為 \(0\) 的實心小圓點表示該出口是死路。

小明以遞迴的方式，先探訪 \(2\) 號石室以下的所有石室，再探訪 \(8\) 號石室以下的所有石室，最後探訪完 \(1\) 號石室以下的所有石室後回到起點。探訪的紀錄為：「\(5\) \(2\) \(10\) \(0\) \(0\) \(0\) \(8\) \(0\) \(0\) \(1\) \(7\) \(0\) \(0\) \(0\) \(0\) \(6\) \(0\) \(0\)」。

本例中的相連石室有：\((5, 2)\)、\((5, 8)\)、\((5, 1)\)、\((2, 10)\)、\((1, 7)\) 與 \((1, 6)\) 共六對，所求的編號差值總和為 \(|5 - 2| + |5 - 8| + |5 - 1| + |2 - 10| + |1 - 7| + |1 - 6| = 29\)。

輸入格式

輸入一行，由若干個非負整數組成，表示小明的紀錄，相鄰兩數之間以一個空白間隔。石室的個數不超過 \(10^5\)，每間石室的編號皆不相同且為不超過 \(10^5\) 的正整數，石室最深的層數不超過 \(40\) 層。

輸出格式

輸出一個整數，為所有相連石室編號差值的絕對值總和。答案可能超過 \(2^{31}\)。

範例一的石室結構如下圖：

範例輸入 1

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

範例輸出 1

26

範例輸入 2

5 2 10 0 0 0 8 0 0 1 7 0 0 0 0 6 0 0

範例輸出 2

29

範例說明 2

此為題目中所述之範例。

評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制均為 \(1\) 秒，Python 程式的執行時間限制為 \(2\) 秒，依正確通過測資筆數給分。若 \(n\) 為石室的數量，其中：

• 第 1 子題組 20 分：\(n \le 20\)，石室編號均為正偶數，且起點石室的所有出口都通往另一個石室，而其它石室最多只有一個出口通往其他石室。如範例一。
• 第 2 子題組 20 分：\(n \le 10^3\)。
• 第 3 子題組 60 分：無額外限制。

題目來源

APCS 程式實作中高級題本範例，程式實作 2022 年 10 月。