POJ 3414 Pots【BFS】+ Python

原题链接：

3414 -- Pots 

参考资料：
POJ 3414 - Pots | 眈眈探求
POJ 3414 Pots【BFS】【图搜】 - it610.com

一 特别注意：

1. 每一种操作对应于一个子节点，并且该子节点具有多种状态，包括：

1.1 A瓶溶液体积

1.2 B瓶溶液体积

1.3 操作类型

1.4 步数

1.5 父节点

PS：将以上各状态存储在一个字典中，将该字典作为一个子节点。

二 代码实现：

## 本代码的节点是结构体
# https://exp-blog.com/algorithm/poj/poj3414-pots/
# https://www.it610.com/article/4935648.htm
import collections

def bfs(graph,A,B,C):
    # 设置节点的初始信息
    # s = graph
    graph['a'] = 0 #瓶子a的初始值
    graph['b'] = 0 #瓶子b的初始值
    # graph['pre'] = -1  # 前一**
    graph['step'] = 0  # 记录步数
    graph['flag'] = None  # 记录操作类型
    graph['parent'] = None # 设置父节点
    # 存储已访问过的节点
    visited = set()
    visited.add(str(graph['a']) + str(graph['b']))
    # 关于队列的参数
    front = 0
    rear = 0
    queue = []
    queue.append(graph) #加入到队列中，作为当前节点
    ## 记录其父节点
    # parent = []
    # parent.append(graph)
    ## 开始处理
    while len(queue) >0:
        # 弹出节点
        vertex = queue.pop(0)
        if vertex['a']==C or vertex['b'] == C:
            # return vertex,parent
            return vertex
        # 获取邻接点，共涉及6种操作，因此得到6个子节点（每一次操作对应于一个子节点）
        for i in range(6):
            nodes= {}
            if i==0:
                # 执行：对a加满
                nodes['a'] = A  # 加满瓶子a
                nodes['b'] = vertex['b']  # 保持不变
                nodes['flag'] = 0  # 操作类型
            elif i == 1:
                # 执行：对b加满
                nodes['a'] = vertex['a']  # 保持不变
                nodes['b'] = B  # 加满瓶子b
                nodes['flag'] = 1  # 操作类型
            elif i == 2:
                # 执行：对a清空
                nodes['a'] = 0  # 清空a
                nodes['b'] = vertex['b']  # 保持不变
                nodes['flag'] = 2  # 操作类型
            elif i == 3:
                # 执行：对b清空
                nodes['a'] = vertex['a']  # 保持不变
                nodes['b'] = 0  # 清空b
                nodes['flag'] = 3  # 操作类型
            elif i == 4:
                # 执行：将A倒入B
                if vertex['a']+vertex['b'] > B:
                    nodes['a'] = vertex['a'] + vertex['b'] -B # a有剩余
                    nodes['b'] = B  # b加满了
                    nodes['flag'] = 4  # 操作类型
                else:
                    nodes['a'] = 0  # a倒空了
                    nodes['b'] = vertex['a'] + vertex['b']  # b未加满
                    nodes['flag'] = 4  # 操作类型
            else:
                # 执行：将B倒入A
                if vertex['a'] + vertex['b'] > A:
                    nodes['a'] = A  # a加满了
                    nodes['b'] = vertex['a'] + vertex['b'] -A  # b有剩余
                    nodes['flag'] = 5  # 操作类型
                else:
                    nodes['a'] = vertex['a'] + vertex['b']  # a未加满
                    nodes['b'] = 0  # b倒空了
                    nodes['flag'] = 5  # 操作类型
            # 每循环一次，判断当前节点：1 是否已经访问过 2 否：加入到已访问，并加入队列中
            if str(nodes['a']) + str(nodes['b']) not in visited:
                # 记录操作步骤
                nodes['step'] = vertex['step'] + 1
                # 添加到已访问列表
                visited.add(str(nodes['a']) + str(nodes['b']))
                # 添加到队列中
                queue.append(nodes)  # 加入到队列中
                # 记录其父节点
                nodes['parent'] = vertex # 这里可以优化
                # parent.append(nodes)
    # return graph, parent
    return graph


## 操作类型
actions = ["FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"]
## 输入
VA,VB,VC = map(int,input().strip().split(' '))
print(VA,VB,VC )
graph = collections.defaultdict(list)
nodes = collections.defaultdict(list)
# parent = collections.defaultdict(list)
# vertex,parent = bfs(graph,VA,VB,VC)
vertex = bfs(graph,VA,VB,VC)
steps = vertex['step']
print(steps) # 涉及的总步数

Show_actions = []
Show_actions.append(vertex['flag'])
temp = vertex
for i in range(steps-1):
    temp = temp['parent']
    Show_actions.append(temp['flag'])

for i in range(steps-1,-1,-1):
    print(actions[Show_actions[i]])

输入：

3 5 4

输出：

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)