class node: # 創(chuàng)建樹(shù)節(jié)點(diǎn)
 def __init__(self, data):
  self.data = data # 存儲(chǔ)三個(gè)壺的容量狀態(tài)
  self.per = None # 存儲(chǔ)上一時(shí)刻三個(gè)壺的容量狀態(tài)

def pour(n): # 擴(kuò)展子節(jié)點(diǎn)
 r_list = n.data # 記錄當(dāng)前三個(gè)水壺的容量狀態(tài)
 max_list = [8, 5, 3] # 水壺的最大容量
 for i, j in ((0, 1), (0, 2), (1, 2), (1, 0), (2, 0), (2, 1)):
  if r_list[i] != 0:
   n_list = r_list.copy() # 初始化下一結(jié)點(diǎn)的水壺狀態(tài)
   if r_list[i] + r_list[j] > max_list[j]:
    n_list[i] = r_list[i] - (max_list[j] - r_list[j])
    n_list[j] = max_list[j]
   else:
    n_list[j] = r_list[i] + r_list[j]
    n_list[i] = 0
   flag = True # 記錄水壺的狀態(tài)是否已經(jīng)發(fā)生過(guò)（擴(kuò)展過(guò)）
   for one in closed_list:
    if one.data == n_list: # 比較當(dāng)前水壺狀態(tài)和以往記錄過(guò)得水壺狀態(tài)
     flag = False
   if flag:
    print("擴(kuò)展的新節(jié)點(diǎn)是：",n_list)
    new_node = node(n_list) # 創(chuàng)建新節(jié)點(diǎn)存儲(chǔ)水壺的新?tīng)顟B(tài)
    new_node.per = n
    open_list.append(new_node)

def BFS_node(root_1): # 遞歸查找子節(jié)點(diǎn)的擴(kuò)展?fàn)顟B(tài)以及查驗(yàn)是否找到4品脫的水壺
 n = root_1
 print("當(dāng)前節(jié)點(diǎn)：",n.data)
 if open_list is None:
  return "沒(méi)有找到4品脫的水"
 nodelist = n.data
 if 4 in nodelist:
  print("找到了4品脫的水")
  print_node(n)
  return "找到了4品脫的水"
 closed_list.append(open_list.pop(0))
 pour(n)
 print("*******")
 BFS_node(open_list[0])

def print_node(n): # 打印正確的水壺操作路徑
 if n.per == None:
  return ""
 print(n.data)
 print_node(n.per)


# 初始化數(shù)據(jù)
root = node([8, 0, 0])
open_list = [root] # 存儲(chǔ)已找到卻未被擴(kuò)展的子節(jié)點(diǎn)
closed_list = [] # 存儲(chǔ)已找到且被擴(kuò)展的子節(jié)點(diǎn)
BFS_node(open_list[0])