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

好的，这里是一个简单的数据结构实现的农夫过河问题的代码：

# 农夫过河问题

# 定义状态类
class State:
    def __init__(self, farmer, wolf, sheep, cabbage):
        self.farmer = farmer
        self.wolf = wolf
        self.sheep = sheep
        self.cabbage = cabbage

    def __eq__(self, other):
        return self.farmer == other.farmer and self.wolf == other.wolf and self.sheep == other.sheep and self.cabbage == other.cabbage

    def __str__(self):
        return "Farmer:{} Wolf:{} Sheep:{} Cabbage:{}".format(self.farmer, self.wolf, self.sheep, self.cabbage)

# 定义搜索函数
def search(initialState, goalState):
    visited = set()
    queue = [[initialState]]
    while queue:
        path = queue.pop(0)
        state = path[-1]
        if state == goalState:
            return path
        if state not in visited:
            visited.add(state)
            for nextState in getNextStates(state):
                newPath = path + [nextState]
                queue.append(newPath)

# 定义获取下一个状态的函数
def getNextStates(state):
    nextStates = []
    if state.farmer == "left":
        if state.wolf == "left":
            nextState = State("right", "right", state.sheep, state.cabbage)
            if isStateValid(nextState):
                nextStates.append(nextState)
        if state.sheep == "left":
            nextState = State("right", state.wolf, "right", state.cabbage)
            if isStateValid(nextState):
                nextStates.append(nextState)
        if state.cabbage == "left":
            nextState = State("right", state.wolf, state.sheep, "right")
            if isStateValid(nextState):
                nextStates.append(nextState)
        nextState = State("right", state.wolf, state.sheep, state.cabbage)
        if isStateValid(nextState):
            nextStates.append(nextState)
    else:
        if state.wolf == "right":
            nextState = State("left", "left", state.sheep, state.cabbage)
            if isStateValid(nextState):
                nextStates.append(nextState)
        if state.sheep == "right":
            nextState = State("left", state.wolf, "left", state.cabbage)
            if isStateValid(nextState):
                nextStates.append(nextState)
        if state.cabbage == "right":
            nextState = State("left", state.wolf, state.sheep, "left")
            if isStateValid(nextState):
                nextStates.append(nextState)
        nextState = State("left", state.wolf, state.sheep, state.cabbage)
        if isStateValid(nextState):
            nextStates.append(nextState)
    return nextStates

# 定义判断状态是否可达的函数
def isStateValid(state):
    if state.sheep == state.wolf and state.farmer != state.sheep:
        return False
    if state.cabbage == state.sheep and state.farmer != state.cabbage:
        return False
    return True

# 测试
initialState = State("left", "left", "left", "left")
goalState = State("right", "right", "right", "right")
path = search(initialState, goalState)
for state in path:
    print(state)

这个代码使用了状态类来表示每个状态，使用 BFS 搜索算法来搜索可行路径，并使用一个 `isStateValid` 函数来判断状态是否可达。