狼兔草过河Python编程代码

在Python中，"狼兔草过河"是一个经典的问题，通常用作算法教学中的例子，特别是广度优先搜索（BFS）或动态规划。这个问题描述的是在一个有河流的地图上，狼、兔子和草分别代表三种不同的角色，它们的目标是在不违反特定条件（狼不吃兔子，兔子不吃草，三者都不吃对方，草能无限生长）的情况下过河。

以下是一个简单的Python版本的解决方案，使用了列表来表示地图状态：

# 定义初始状态和目标状态
river = ['#', '#', '#']  # 河流，用'#'表示水域
wolf, rabbit, grass = 'W', 'R', 'G'  # 狼、兔子和草的标记

def move(direction, positions):
    # 更新角色位置
    if direction == 'L':  # 向左
        new_positions = [positions[i] if i % 3 != 0 else '#' for i in range(3)]
    elif direction == 'R':  # 向右
        new_positions = [positions[i] if i % 3 != 2 else '#' for i in range(3)]
    else:  # 上下移动
        new_positions = [positions[i - 1] if i > 0 else '#' for i in range(3)]
    return new_positions

def can_cross(positions):
    # 检查角色能否安全移动
    return positions[1] != '#' and positions != wolf and positions != rabbit

def solve(start, end):
    positions = start.copy()
    queue = [(positions, '')]
    visited = set()

    while queue:
        positions, path = queue.pop(0)
        if positions == end:
            return path
        if positions not in visited:
            visited.add(positions)

            for direction in ['U', 'D', 'L', 'R']:
                next_positions = move(direction, positions)
                if can_cross(next_positions):
                    queue.append((next_positions, path + direction))

# 示例地图，假设起始位置是WRG（狼在左，兔子在中间，草在右）
start = ['#', 'W', 'R', 'G', '#', '#']
end = ['#', 'G', 'R', 'W', '#', '#']

solution = solve(start, end)
print(f"狼兔草过河的路径: {solution}")