python-APCS-2022/10/23實作第三題:石窟探險
===
### ZeroJudge:j124石窟探險
### <font color="#FFCC22">題目是樹狀圖??那我們就真的直接建立一棵樹來完成</font>
### [解法2在這裡](https://hackmd.io/@Aji-Hsu/BJUZgd92i)
---
\
\
\
\
\
\
<font color="#FFEE99">**1想法邏輯**</font>
---
https://zerojudge.tw/ShowProblem?problemid=j124
https://zerojudge.tw/ShowImage?id=2500

(可以搭配第2大點和第3大點一起看)
1.(1-1)從頂點2開始看，2因為是偶數，所以要預留兩個位子用來存放接下來會輸入的node，此時人在石窟2當中
2.(1-2)下一個輸入的是6，接在2的下一個，此時人已經跑到石窟6裡面了
3.(1-3)根據(1-2)一直跑下去，到達石窟14的時候會碰到盡頭，這個時候就要往上走，走到石窟8，只要碰到就回走
4.(1-4)我們可以發現，所有石窟的差是(1-2)走訪時的差距總和

\
\
\
<font color="#FFEE99">**2如何建立一個雙向的樹**</font>
---
1.at用來存放每個node的數字
2.parent用來存放每一個node的上一個node，如果是head的話，那就是None，用來實現(1-3)的往回走
3.next用來存放下一個node，有next和parent這就是一個雙向的樹了
4.line14的isFull方法是判斷，這邊是不是盡頭，當(1-2)走到盡頭時，就是用這個判斷的
5.line22的findIndex是幫助存放node用到的方法
ex.當next = [node8, node2, None]他就會回傳None的索引值2

class Tree:
    def __init__(self, num):
        self.at = num
        self.parent = None
        if num == 0:
            pass
        else:
            if num % 2 == 0:
                self.next = [None]*2
            else:
                self.next = [None]*3

    def isFull(self):
        if self.at % 2 == 0:
            if (self.next[0] is not None) and (self.next[1] is not None):
                return True
        else:
            if (self.next[0] is not None) and (self.next[1] is not None) and (self.next[2] is not None):
                return True
        return False

    def findIndex(self):
        for i in self.next:
            if i is None:
                return self.next.index(i)

\
\
\
<font color="#FFEE99">**3主程式**</font>
---
1.line2到4是用來實現(1-1)
2.line5的total是存放走訪時的差總和
3.line8實現(1-3)
4.line10用來處理輸入為0的情況
5.line14實現(1-2)
:::info
註:ptr是用來指向節點的變數，人在走訪的時候，ptr就代表那個人
為什麼一定要用ptr指向:因為從我的寫法可以得知，在我新增node時的data是用完就丟的，所以如果沒有ptr幫忙，我就找不到節點了
:::

Nums = [int(i)for i in input().split()]
head = Tree(Nums[0])
ptr = head
ptr.parent = None
total = 0

for i in Nums[1:]:
    while ptr.isFull():
        ptr = ptr.parent
    if i == 0:
        ptr.next[ptr.findIndex()] = 0
        continue

    data = Tree(i)
    data.parent = ptr
    ptr.next[ptr.findIndex()] = data
    total += abs(ptr.at - data.at)
    ptr = data

print(total)

\
\
\
<font color="#FFEE99">**完整程式碼**</font>
---

class Tree:
    def __init__(self, num):
        self.at = num
        self.parent = None
        if num == 0:
            pass
        else:
            if num % 2 == 0:
                self.next = [None]*2
            else:
                self.next = [None]*3

    def isFull(self):
        if self.at % 2 == 0:
            if (self.next[0] is not None) and (self.next[1] is not None):
                return True
        else:
            if (self.next[0] is not None) and (self.next[1] is not None) and (self.next[2] is not None):
                return True
        return False

    def findIndex(self):
        for i in self.next:
            if i is None:
                return self.next.index(i)


Nums = [int(i)for i in input().split()]
head = Tree(Nums[0])
ptr = head
ptr.parent = None
total = 0

for i in Nums[1:]:
    while ptr.isFull():
        ptr = ptr.parent
    if i == 0:
        ptr.next[ptr.findIndex()] = 0
        continue

    data = Tree(i)
    data.parent = ptr
    ptr.next[ptr.findIndex()] = data
    total += abs(ptr.at - data.at)
    ptr = data

print(total)

###### tags: `題解`
###### tags: `APCS`
###### tags: `python`