商人渡河

三名商人各带一个随从乘船渡河。现此岸有一小船只能容纳两人，由他们自己划行。若在河的任一岸随从人数比商人多，他们就可能抢劫财物。不过如何乘船渡河的大权由商人们掌握。商人们怎样才能安全过河呢?

• 思路

1. 找到每一次小船可能的集合
2. 统计岸边，商人数量和随从可能的集合
3. 每移动一次，重新统计岸边人数，判断是否在集合2中，如果是，纪录路线，如果不是pass.

import os
import sys
import copy

N = 3               # Total people number
END = [0, 0]        # destation point

# goble decison
src_decision = [[-2,0], [-1,0], [-1,-1], [0,-1], [0,-2]]
dst_decision = [[1,0], [2,0], [1,1], [0,1],[0,2]]

# global AVAIABLE point
restrict_point_list = []

# global list to record suceess path
result_path = []

def init_restrict_point():
    for y in range(0,N+1):
        a = [0,y]
        restrict_point_list.append(a)
    for x in range(1,N):
        a = [x,x]
        restrict_point_list.append(a)
    for y in range(0,N+1):
        a = [N,y]
        restrict_point_list.append(a)
init_restrict_point()
print(restrict_point_list)

def SearchCrossRiver(start_p, derict, src_reached, dst_reached):
    # 深拷贝，子改父不改
    s_reached = copy.deepcopy(src_reached)
    d_reached = copy.deepcopy(dst_reached)
    if derict == 1:
        # 把开始的坐标加入list
        if start_p not in s_reached:
            s_reached.append(start_p)
        for decison in src_decision:
            point = []
            # 修改后的坐标
            for i in range(2):
                point.append(start_p[i]+decison[i])
            # 修改后的坐标==[0，0]结束循环
            if point == END:
                print ("It succesed !!")
                result_path.append(s_reached)
                result_path.append(d_reached)
                print(result_path)
                return 0
            elif (point in restrict_point_list) and (point not in d_reached):
                # 此岸和对岸来回迭代
                SearchCrossRiver(point, -1, s_reached, d_reached)
            else:
                pass
        return 1
    elif derict == -1:
        if start_p not in d_reached:
            d_reached.append(start_p)
        for decison in dst_decision:
            point = []
            for i in range(2):
                point.append(start_p[i] + decison[i])
            if point == END:
                result_path.append(s_reached)
                result_path.append(d_reached)
                return 0
            elif (point in restrict_point_list) and (point not in s_reached):
                SearchCrossRiver(point, 1, s_reached, d_reached)
            else:pass
        return 1
    else:
        print ("error")
        return 2
def find_function():
    start_point = [N,N]     # starting point
    init_restrict_point()

    src_reached_list = []
    dst_reached_list = []

    result = SearchCrossRiver(start_point, 1, src_reached_list, dst_reached_list)
    print ("result = ", result_path)
    print ('\n')

if __name__ == '__main__':
    find_function()