k862. 輩份比較

        假設B,C是A的祖先，D,E是A的子孫,F是E的子孫，如果我們先忽略輩分這件事情，單純從A點走到F，那就是一個單純的BFS就可以解決的事情，只要在BFS的基礎上，讓每個節點記錄自己的父輩與子孫輩的成員即可。

下列附上程式碼：

class Node:
    def __init__(self):
        self.father = []
        self.child = []
        self.dis = -99999999


s = set()
n = int(input())
d = {}
for i in range(n):
    c,f = input().split()
    if c not in d:
        d[c] = Node()
    if f not in d:
        d[f] = Node()
    d[c].father.append(f)
    d[f].child.append(c)
    
start,target = input().split()

d[start].dis = 0
p = [start]
keep = True
while keep:
    for i in p:
        for j in d[i].father:
            if j not in s:
                s.add(j)
                d[j].dis = d[i].dis-1
                p.append(j)
                if j == target:
                    keep = False
                    break
        for j in d[i].child:
            if j not in s:
                s.add(j)
                d[j].dis = d[i].dis+1
                p.append(j)
                if j == target:
                    keep = False
                    break
        if keep == False: break
print(d[target].dis)

APCS 2024.01 m933. 3. 邏輯電路

        乍看之下，本來覺得可以直接硬解，所以沒多想便用了很多清單來解題，沒想到過程中發現要記錄的資訊量很大，寫著寫著程式越來越複雜，所幸從頭開始，運用自訂結構，將每個節點所需要的欄位明確定義出來，這題就會簡單許多。

        解題技巧運用到BFS再加上一些條件式判斷，依下圖為例：

        第0步的起點為g1,g2,g3,g4,g5，第一步的起點為g6,g7,g8,g9,第二步的起點為g6,g10,g11,第三步為g11，你會發現第一步的g6沒有馬上走到g12，這也是這題的重點之一，因為第一次走到g1->g6的時候，g6還算不出答案，它還在等待g7->g6，因為g6必須湊齊g1,g7才能得到輸出。

        以下附上完整程式：

class Node:
    def __init__(self):
        self.nexts = []#該節點是那些節點的輸入
        self.val = -1
        self.delay = 0
        self.gate = None
        self.ipt = []#那些節點是本節點的輸入

def t():
    pp,q,r,m = [int(i) for i in input().split()]
    p = [int(i) for i in input().split()]
    t = [int(i) for i in input().split()]
    nodes = []
    for i in range(pp+q+r):
        nodes.append(Node())
    for i in range(pp):
        nodes[i].val = p[i]
    for i in range(pp , pp+q):
        nodes[i].gate = t[i-pp]
    #print(nodes)
    
    for i in range(m):
        a,b = [int(i) for i in input().split()]
        a -= 1
        b -= 1
        nodes[a].nexts.append(b)
    
    p = [i for i in range(pp)]
    
    '''1 為 AND、2 為 OR、3 為 XOR、4 為 NO'''
    for i in p:
        if nodes[i].val == -1:continue
        for j in nodes[i].nexts:#i節點是j節點的輸入
            nodes[j].ipt.append(i)#j節點的輸入有添加i節點
            if nodes[j].gate == 4 and len(nodes[j].ipt) == 1:
                nodes[j].val = int(not nodes[nodes[j].ipt[0]].val)#j節點的值，是j的輸入的值的相反
                nodes[j].delay = nodes[nodes[j].ipt[0]].delay + 1
                p.append(j)
            elif nodes[j].gate != 4 and len(nodes[j].ipt) == 2:
                p1,p2 = nodes[nodes[j].ipt[0]] , nodes[nodes[j].ipt[1]]
                if nodes[j].gate == 1:
                    nodes[j].val = int(p1.val and p2.val)
                if nodes[j].gate == 2:
                    nodes[j].val = int(p1.val or p2.val)
                if nodes[j].gate == 3:
                    nodes[j].val = int(p1.val != p2.val)
                nodes[j].delay = max(p1.delay , p2.delay) + 1
                p.append(j)
    mm = 0
    for i in range(pp+q , pp+q+r):
        mm = max(nodes[nodes[i].ipt[0]].delay , mm)
    print(mm)
    for i in range(pp+q , pp+q+r):
        print(nodes[nodes[i].ipt[0]].val , end = ' ')
    print()
t()

        如果有問題，歡迎留言會email我。