编辑代码

# coding:utf-8
#JSRUN引擎2.0,支持多达30种语言在线运行,全仿真在线交互输入输出。 
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。
    """
    # 定义三个瓶子的容量:A=10两, B=7两, C=3两
    capacities = (10, 7, 3)
    # 初始状态:A 满,B、C 空
    initial = (10, 0, 0)
    # 使用队列进行广度优先搜索
    queue = deque([initial])
    # 记录已访问的状态,防止重复搜索
    visited = {initial}
    # 用字典记录每个状态的前驱状态和进行的倒油操作
    # 格式:state: (prev_state, (from, to, pour_amount))
    parent = {initial: None}
    move_taken = {initial: None}

    while queue:
        state = queue.popleft()
        # 判断是否达到目标状态:A 瓶中有5两
        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

        # 遍历所有可能的倒油操作(从 i 倒到 j)
        for i in range(3):
            for j in range(3):
                if i == j:
                    continue
                # 如果 i 瓶中没有油或者 j 瓶已满则跳过
                if state[i] == 0 or state[j] == capacities[j]:
                    continue
                # 计算本次能倒出的油量:取 i 瓶剩余和 j 瓶可装容量中的较小者
                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)

    # 若搜索完毕均未找到目标状态,返回 None
    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)