"""
问题描述：

有三个和尚和三个妖怪，他们要利用唯一一条小船过河，这条小船一次最多只能载两个人，
同时，无论是在河的两岸还是船上，只要妖怪的数量大于和尚的数量，妖怪们就会将和尚吃掉。
现在需要选择一种过河的安排，保证和尚和妖怪都能过河且和尚不能被妖怪吃掉。。
"""

import sys


def can_cross(state, act):
    """检查当前状态下，是否可以进行渡河操作
       可以渡河的条件：渡河后两岸剩余妖怪数不能大于人数
    """
    result = True
    if act[0]!=state[0] or act[1]+act[2]==0 or act[1]+act[2]>2: # 船不在同一边或空船或超过2个，失败
        result = False
    new_state = state[:]
    if act[0] == 1:  # 从此岸到对岸
        new_state[0] = 0
        new_state[1] = state[1] - act[1]
        new_state[2] = state[2] - act[2]
        new_state[3] = state[3] + act[1]
        new_state[4] = state[4] + act[2]
    else:
        new_state[0] = 1
        new_state[1] = state[1] + act[1]
        new_state[2] = state[2] + act[2]
        new_state[3] = state[3] - act[1]
        new_state[4] = state[4] - act[2]
    for i in range(1,5):
        if new_state[i] < 0:
            result = False
    if new_state[2] > 0 and new_state[1] > new_state[2]:
        result = False
    if new_state[4] > 0 and new_state[3] > new_state[4]:
        result = False
    return result


def do_cross(state, act):
    """执行渡河操作
       返回操作后的状态
    """
    new_state = state[:]
    if act[0]==1: # 从此岸到对岸
        new_state[0] = 0
        new_state[1] = state[1] - act[1]
        new_state[2] = state[2] - act[2]
        new_state[3] = state[3] + act[1]
        new_state[4] = state[4] + act[2]
    else:
        new_state[0] = 1
        new_state[1] = state[1] + act[1]
        new_state[2] = state[2] + act[2]
        new_state[3] = state[3] - act[1]
        new_state[4] = state[4] - act[2]
    return new_state


def cross(state_list):
    """用递归法完成深度搜索"""
    global plancount
    cur_state = state_list[-1][:] # 当前状态
    for x in range(2):
        for y in range(3):
            for z in range(3):
                # 用三重循环测试所有不同的倒水方法
                act = [x, y, z]
                if can_cross(cur_state, act):
                    new_state = do_cross(cur_state, act)
                    if new_state not in check_list:
                        # 新的状态不能是以前出现过的
                        # 加入新的状态
                        check_list.append(new_state)
                        state_list.append(new_state)
                        act_list.append(act[:])
                        # 检查是否达到最终状态
                        if new_state == [0, 0, 0, 3, 3]:
                            plancount += 1
                            print("\n第{:d}方案, 共{:d}步".format(plancount, len(act_list)))
                            print("状态[船,妖,人,妖,人]    渡河动作")
                            for i in range(len(act_list)):
                                print(state_list[i], end="")
                                if act_list[i][0]==1:
                                    print("        ->  ", end="")
                                else:
                                    print("        <-  ", end="")
                                print("{:d}妖{:d}人".format(act_list[i][1], act_list[i][2]))
                            print(state_list[-1])
                        else:
                            cross(state_list)

                        # 恢复状态
                        check_list.pop()
                        state_list.pop()
                        act_list.pop()


if __name__ == '__main__':
    state_list = [] # 状态变化列表，保存从[1, 3, 3, 0, 0, 1]到[0, 0, 0, 3, 3]的过程
                     # 状态分别表示船的位置（1在此岸，0在对岸）,此岸妖怪数，和尚数，对岸妖怪数，和尚数
    state_list.append([1, 3, 3, 0, 0])
    act_list = [] # 动作列表（船方向, 船上妖怪数，船上和尚数） 船方向1表示从此岸到对岸，0表示从对岸来到此岸
    check_list = [] # 检查状态列表，保存已经出现的状态，以防止出现状态循环
    check_list.append([1, 3, 3, 0, 0])
    plancount = 0 # 方案数
    cross(state_list)