引言
【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》，书中是用Ruby实现的。这里是用python来实现。
问题描述
现在有很多制造商都在卖扫地机器人，可是这些机器人有时候会反复清扫某一个地方。假设有一款机器人不会反复清扫同一个地方，它只能前后左右移动。举个例子，如果第1次向后移动，那么连续移动3次时，就会有以下9种情况（见图）。又因为第1次移动可以是前后左右4种情况，所以移动3次时全部路径有 9 * 4 = 36 种。那么求这个机器人移动12次时，有多少种移动路径？（P029）
思路
用坐标(0,0)表示最初的位置，python中用[0,0]表示。则前后左右的移动分别表示为[0, 1], [0, -1], [-1, 0], [1, 0]。
记trace为移动路径的列表，即上图第1条移动路径表示为trace=[[0, 0], [0, -1], [0, -2], [0, -3]]，图中最后一条移动路径表示为trace=[[0, 0], [0, -1], [-1, -1], [-2, -1]]。
假如前两次的移动路径是trace=[[0, 0], [0, -1], [0, -2]]，那么第三次移动有3种情况，分别是上图中(1)、(2)、(3)这三种情况。如何来判断呢？
移动方式有operator = [[0, 1], [0, -1], [-1, 0], [1, 0]]，第3次移动任选一种（每一种都有可能，这里就需要遍历了）。
假设第3次移动方式选择[0,1]即向上移动，上次(这里是第2次)移动到位置是trace[-1]即这里是[0,-2]。那么第三次移动后的位置为[0+0,-2+1]即[0,-1]，而这个位置在trace中已经包含了，因此第3次的移动选择[0,1]不合适。
如果第3次移动方式选择[0,-1]即向下移动，上次(这里是第2次)移动到位置是trace[-1]即这里是[0,-2]。那么第三次移动后的位置为[0+0,-2-1]即[0,-3]，而这个位置不在trace中，因此第3次的移动可以选择[0,-1]，这样新的trace就为new_trace=[[0, 0], [0, -1], [0, -2],[0,-3]]，即上图中的(1)。
同样如果第3次移动方式选择[-1,0]即向左移动，上次(这里是第2次)移动到位置是trace[-1]即这里是[0,-2]。那么第三次移动后的位置为[0-1,-2+0]即[-1,-2]，而这个位置也不在trace中，因此第3次的移动也可以选择[-1,0]，这样新的trace就为new_trace=[[0, 0], [0, -1], [0, -2],[-1,-2]]，即上图中的(3)。
同样如果第3次移动方式选择[1,0]即向右移动，上次(这里是第2次)移动到位置是trace[-1]即这里是[0,-2]。那么第三次移动后的位置为[0+1,-2+0]即[1,-2]，而这个位置也不在trace中，因此第3次的移动也可以选择[1,0]，这样新的trace就为new_trace=[[0, 0], [0, -1], [0, -2],[1,-2]]，即上图中的(2)。
这样，把符合条件的移动路径放入一个列表trace_lists，等移动遍历完之后trace_lists就包含了所有满足条件的移动路径了。
python3实现
def move(trace,operator,n): # trace为移动路径，operator为移动方式，n表示连续移动n次。
if len(trace) == n + 1: # 递归的跳出条件，如果trace的长度满足了n次移动后，则结束
return 1
last = trace[-1]
for i in range(len(operator)):# 遍历每次的移动方式
next_oper = operator[i]
next_place = [j+k for j,k in zip(last, next_oper)] # 获取当次移动后的位置
if next_place not in trace:
# 如果当次移动后的位置不在当次移动之前的移动路径，则该次移动符合要求，生成新的移动路径new_trace，进行下一次移动
new_trace = trace.copy()
new_trace.append(next_place)
if(len(new_trace) == n + 1):
global trace_lists
trace_lists.append(new_trace)
move(new_trace,operator,n)
当连续移动3次时，共有36种移动路径。
要看具体移动路径，只需输出trace_lists即可
那么这个机器人移动12次时，有多少种移动路径？
即有324932种。
