农夫过河Python

农夫过河的问题通常是一个经典的算法题目，它涉及到了动态规划在实际问题中的应用。假设农夫有一头牛，需要将它们都安全地从一岸运送到另一岸。问题是，船每次只能承载一个人和一头牛，但当一个人和牛都在一艘船上时，如果水位上涨，牛会把人淹死。因此，农夫必须保证任何时候都有足够的船员控制船只。

在 Python 中，我们可以用递归的方式来解决这个问题，定义一个函数来表示当前的状态（农夫、牛和哪边是安全的），然后考虑所有可行的移动，比如让农夫过去，让牛过去，或者两边都不动。最终找到一种状态转移策略，使得所有人都能安全到达对岸。

这是一个简单的示例代码：

def ferry_crossing(farmer, cow, left, right):
    if farmer and cow in (left, right):  # 如果有农民和牛同时在一边，无法过河
        return False
    elif not farmer and cow == left:   # 如果只有牛在左边，农民可以过去接牛
        return [farmer, cow] == [right, None]
    elif not cow and farmer in (left, right):  # 如果只有农民在，他可以直接过去
        return True

    # 分别尝试两种情况：农民过河或者牛过河
    options = [
        ferry_crossing(True, False, farmer, left),  # 农民过河，留下牛
        ferry_crossing(False, True, cow, left),     # 牛过河，留下农民
    ]

    # 检查两种情况是否可行，然后返回结果
    for option in options:
        if option:  # 可行，继续探索其他路径
            return option + ferry_crossing(False, False, farmer, right)
    else:  # 所有选项都不行，返回False
        return False

# 初始化：农民在左岸，牛在右岸
solution = ferry_crossing(True, False, 'A', 'B')
if solution:
    print("Solution found:", solution)  # 输出如何过河的具体步骤
else:
    print("No solution.")