数据结构解决农夫过河问题代码

以下是使用 Python 语言实现的农夫过河问题的代码：

def is_valid(state):
    """判断状态是否合法"""
    if state[1] == state[2] and state[0] != state[1]:
        return False
    if state[0] == state[1] and state[0] != state[2]:
        return False
    return True

def move(state, item):
    """将物品移动到另一边"""
    new_state = list(state)
    new_state[0] = 1 - new_state[0]  # 将船移动到另一边
    new_state[item] = 1 - new_state[item]  # 将物品移动到另一边
    return tuple(new_state)

def dfs(state, path, visited):
    """使用深度优先搜索求解问题"""
    if state == (1, 1, 1):  # 找到了一组解
        print(path)
        return True
    visited.add(state)
    for i in range(3):
        if state[i] == state[0]:  # 物品在同一边
            new_state = move(state, i)
            if is_valid(new_state) and new_state not in visited:
                if dfs(new_state, path + [(i, state[0])], visited):
                    return True
    return False

dfs((0, 0, 0), [], set())

该代码使用深度优先搜索算法实现，其中 `is_valid` 函数用于判断状态是否合法，`move` 函数用于将物品移动到另一边，`dfs` 函数用于使用深度优先搜索算法求解问题。具体而言，`dfs` 函数首先判断当前状态是否是目标状态，如果是则输出路径并返回 `True`，否则遍历每个物品，如果该物品和农夫在同一边，则将该物品移动到对岸，然后判断新状态是否合法并且是否已经被访问过，如果是则递归搜索该状态。