过河问题 python DFS

过河问题是一个经典的递归/深度优先搜索问题。以下是一个使用Python实现的深度优先搜索算法来解决过河问题的示例代码：

def can_cross_river(bank):
    # 检查是否所有人都过河
    return all(x == 0 for x in bank)

def is_valid_move(bank):
    # 检查是否会有人被吃掉
    if bank[0] != bank[1] and bank[1] == bank[2]:
        return False
    if bank[2] != bank[3] and bank[3] == bank[4]:
        return False
    return True

def dfs(bank, path):
    if can_cross_river(bank):
        # 所有人都过河，输出路径
        print(path)
        return
    
    for i in range(len(bank)):
        for j in range(i + 1, len(bank)):
            # 选择两个人过河
            new_bank = list(bank)
            new_bank[i] = new_bank[j] = 1 - new_bank[j]
            
            if is_valid_move(new_bank):
                # 进行合法移动
                new_path = list(path)
                new_path.append(new_bank)
                dfs(new_bank, new_path)

# 初始状态：0代表在左岸，1代表在右岸
initial_bank = [0, 0, 0, 0, 0]
initial_path = [initial_bank]

dfs(initial_bank, initial_path)

以上代码使用了深度优先搜索算法来找到所有可能的过河路径。`bank` 列表表示每个人的位置，0代表在左岸，1代表在右岸。`path` 列表用于记录过河的路径。`can_cross_river` 函数用于检查是否所有人都已经过河。`is_valid_move` 函数用于检查当前状态是否合法。`dfs` 函数是递归的深度优先搜索函数，它会尝试所有可能的移动来找到过河的路径，并输出所有路径。

你可以根据实际需要进行修改和调整，例如添加更多的限制条件或者优化算法。希望能对你有所帮助！