from collections import deque
from typing import Optional, List, Tuple
BOTTLE_NAMES = ['A(10两)', 'B(7两)', 'C(3两)']
def bfs() -> Optional[List[Tuple[Tuple[int, int, int], Optional[Tuple[int, int, int]]]]]:
"""
使用广度优先搜索算法来寻找从初始状态到目标状态的倒油路径。
初始状态为 A 瓶满(10 两),B 和 C 瓶空。目标状态为 A 瓶中有 5 两油。
返回值:如果找到路径,返回一个列表,列表元素为 (状态, 倒油操作) 的元组;如果未找到,返回 None。
"""
capacities = (10, 7, 3)
initial = (10, 0, 0)
queue = deque([initial])
visited = {initial}
parent = {initial: None}
move_taken = {initial: None}
while queue:
state = queue.popleft()
if state[0] == 5:
path = []
cur = state
while cur is not None:
path.append((cur, move_taken[cur]))
cur = parent[cur]
path.reverse()
return path
for i in range(3):
for j in range(3):
if i == j:
continue
if state[i] == 0 or state[j] == capacities[j]:
continue
amount = min(state[i], capacities[j] - state[j])
new_state = list(state)
new_state[i] -= amount
new_state[j] += amount
new_state = tuple(new_state)
if new_state not in visited:
visited.add(new_state)
parent[new_state] = state
move_taken[new_state] = (i, j, amount)
queue.append(new_state)
return None
def print_solution(solution: Optional[List[Tuple[Tuple[int, int, int], Optional[Tuple[int, int, int]]]]]):
"""
打印倒油问题的解决方案。
参数:solution 为 bfs 函数返回的路径列表,如果为 None 表示未找到解法。
"""
if not solution:
print("未找到解法")
return
print("初始状态为 (A, B, C):(10, 0, 0)")
for idx, (state, move) in enumerate(solution):
if move is None:
continue
from_idx, to_idx, amount = move
print(f"第{idx}步:从 {BOTTLE_NAMES[from_idx]} 倒 {amount} 两 到 {BOTTLE_NAMES[to_idx]},得到状态 {state}")
print("目标状态:A 瓶中正好有 5 两油,实现均分!")
if __name__ == '__main__':
solution = bfs()
print_solution(solution)