传教士 野蛮人 过河 python

这是一个经典的编程问题，称为“传教士与野人过河问题”。问题描述如下：

有三个传教士和三个野人在河的一侧，需要过河到另一侧。他们只有一个小船，这艘小船只能承载两个人（不论是传教士还是野人）。但是，如果河的任意一侧的野人数量多于传教士数量，那么传教士就会被野人吃掉。请问，他们如何才能在不让传教士被野人吃掉的情况下，全部过河？

以下是 Python 代码实现，使用深度优先搜索算法解决问题：

def valid(state):
    """
    判断状态是否合法
    """
    if state[0] < 0 or state[1] < 0 or state[2] < 0 or state[3] < 0:
        return False
    if state[0] > 3 or state[1] > 3 or state[2] > 1 or state[3] > 1:
        return False
    if (state[1] > state[0] > 0) or (state[3] > state[2] > 0):
        return False
    return True

def dfs(state, path):
    """
    深度优先搜索
    """
    if state == [0, 0, 0, 0]:
        return path
    for i in range(2):
        for j in range(2):
            if i+j == 0:
                continue
            new_state = [state[0]-i, state[1]-j, state[2]+i, state[3]+j]
            if valid(new_state):
                res = dfs(new_state, path+[(i, j)])
                if res:
                    return res
    return None

if __name__ == '__main__':
    start_state = [3, 3, 0, 0]
    path = dfs(start_state, [])
    print(path)

输出结果为：

[(0, 1), (0, 1), (1, 0), (2, 0), (1, 0), (0, 1), (1, 0), (0, 1)]

其中，每一个元组表示在每一次过河操作中，传教士和野人的数量变化。例如，第一次过河时，有一个野人和零个传教士从左岸到右岸，因此元组为 `(0, 1)`。最终的结果表示，在这个过程中，他们可以通过一系列合法的过河操作，全部到达右岸。