青蛙过河python版

前几天发了一个青蛙过河https://www.xushine.net/?p=1110

D大的感叹历历在目啊

现在放个python的版本出来~

trace_stack = []

def recursive(frog_list, final_list):
    global trace_stack

    if frog_list == final_list:
        trace_stack.append(frog_list)
        return True

    index = frog_list.index(\’+\’)

    # 空石头右边第一只
    if index+1 < len(frog_list):
        if frog_list[index+1] == \'<\’:
            temp = frog_list[:]
            temp[index],temp[index+1] = temp[index+1],temp[index]
            if recursive(temp, final_list):
                trace_stack.append(frog_list)
                return True

        # 空石头右边第二只
        if index+2 < len(frog_list):
            if frog_list[index+2] == \'<\’:
                temp = frog_list[:]
                temp[index],temp[index+2] = temp[index+2],temp[index]
                if recursive(temp, final_list):
                    trace_stack.append(frog_list)
                    return True

    # 空石头左边第一只
    if index-1 >= 0:
        if frog_list[index-1] == \’>\’:
            temp = frog_list[:]
            temp[index],temp[index-1] = temp[index-1],temp[index]
            if recursive(temp, final_list):
                trace_stack.append(frog_list)
                return True

        # 空石头左边第二只
        if index-2 >= 0:
            if frog_list[index-2] == \’>\’:
                temp = frog_list[:]
                temp[index],temp[index-2] = temp[index-2],temp[index]
                if recursive(temp, final_list):
                    trace_stack.append(frog_list)
                    return True

    return False

def main():
    global trace_stack
    frog_count = 3
    frog_str = \’>\’*frog_count + \’+\’ + \'<\’*frog_count
    frog_list = [i for i in frog_str]
    final_list = frog_list[:]
    final_list.reverse()

    if recursive(frog_list, final_list):
        try:
            while True:
                line = trace_stack.pop()
                print “”.join(line)
        except:
            pass

if __name__ == “__main__”:
    main()