g = {}  # 存放父子节点

statusl = []# 表示方式 [ML, CL, MR, CR, B]   左传教士、左野人、右传教士、右野人、船

route = []  # 一次路径

way = []  # 总路径

actions = [[1, 0], [0, 1], [1, 1], [0, 2], [2, 0]]  # 五种操作方式

def result(s):

    if s[0] < 0 or s[1] < 0 or s[2] < 0 or s[3] < 0:  # 负数

        return

    if (s[0] < s[1] and s[0] != 0) or (s[2] < s[3] and s[2] != 0):  # 传教士被吃

        return

    d = tuple(s)    # 元组作为状态点

    if len(statusl) > 1:

        f = tuple(statusl[-2][:])

        if f in g.keys() and d not in g[f]:

            g[f].append(d)

        else:

            g[f] = [d]

    for k in statusl[:-1]:   # 重复状态

        if k[0] == s[0] and k[1] == s[1] and k[3] == s[3] and k[4] == s[4]:

            return

    mid = [0] * 5

    for j in actions:

        mid[0] = s[0] - j[0] * s[4]

        mid[1] = s[1] - j[1] * s[4]

        mid[2] = s[2] + j[0] * s[4]

        mid[3] = s[3] + j[1] * s[4]

        mid[4] = -s[4]

        statusl.append(mid[:])

        result(mid)   # 判断该动作是否合理，并加入字典

        statusl.pop()

    return

# 深度搜索寻找路径

def dfs(s):

    s = tuple(s)     # 字典的值是列表里面包含元组，原因是字典的键值不能是列表

    if s in route:   # 已经在路径里面

        route.append(s)

        return

    # 到达终点，记录路径

    if s == (0, 0, 3, 3, -1):

        route.append(s)

        way.append(route[:])

        return

    route.append(s)

    for i in range(len(g[s])):

        dfs(g[s][i])   # 递归搜索直到到达终点或者重复

        route.pop()

def main():

    start = [3, 3, 0, 0, 1]

    statusl.append(start)

    result(start)

    dfs(start)

    num = 0   # 统计次数

    # 输出路径

    for k in way:

        num += 1

        print(" 外汇跟单gendan5.com 第 %d 条路径： " % num)

        print(" 左传教士 , 左食人者 , 右传教士 , 右食人者 ,   船 ")

        for i in k:

            print("{}       {}       {}       {}       {}   ".format(i[0], i[1], i[2], i[3], i[4]))

    print(" 总共有 %d 条路径 " % num)

if __name__ == '__main__':

    main()