从左边入口处的“2011”进去，在迷宫里转悠，最后变为“2012”从右边出来。你可以在迷宫里随便转圈，可以重复之前走过的路，但不能直接退回上一次刚刚走过的路。每经过一条路时都需要按照路上的标示立即进行计算。
这是一个广度搜索问题。由于同一条路不能连续走两回，因此已搜索过的状态节点包括三个信息：
- 当前位置：2011处的位置编号为0， 中间处的位置编号为1， 2012处的编号为2。
- 当前的数值。
- 上一步走过的路径。 注意 这个信息容易忽略，若忽略则不能得到正确解答。
从初始状态(0, 2011, “*”)开始，搜索状态(2, 2012, “3”)或(2, 2012, “5”)。其中”*”表示起点。每个状态节点都有几个相邻的状态，例如对于初始状态来说，如果走”+7”路径就到达状态(1,2018,”7”)。由于2011是一个奇数，我们不选择”/2”这条路径。
所谓广度搜索就是将所有与当前状态相邻的状态都放进一个队列中，然后从队列取出下一个状态，并重复上述步骤，直到找到目标状态。为了在搜索到目标状态时，能输出从起点状态开始所走过的路径，队列中的状态会将整个路径保存在起来。
def solve(from_, to_):
queue = deque([(0, from_, "*")]) ❶
visited = set([]) ❷
def next_value(pos, value):
if pos == 0: # 在左边位置时
yield 1, value+7, "7"
if value % 2==0: # 只有当前的值为偶数时才选择除以2这条路
yield 1, value//2, "2"
if pos == 1: # 在中间位置时
yield 0, value+7, "7"
if value % 2==0:
yield 0, value//2, "2"
yield 2, value*3, "3"
yield 2, value-5, "5"
if pos == 2: # 在右边位置时
yield 1, value*3, "3"
yield 1, value-5, "5"
while True:
pos, value, path = queue.popleft()
last = path[-1] # 最后走过的路径
visit = (pos, value, last)
if visit in visited: continue ❸
visited.add(visit) ❹
for p, v, n in next_value(pos, value):
if n != last: ❺
if p == 2 and v == to_: # 如果右边位置，并且值为目标值则返回路径
return path + n
queue.append((p, v, path+n))
path = solve(2011, 2012)
❶程序采用deque队列保存待搜索的状态节点，一开始只包含初始状态。❷为了加快搜索速度，我们使用一个visited集合保存所有访问过的状态节点。每访问一个状态节点，就将(位置, 数值, 最后走过的路径)存放到visited集合之中。❸如果从队列中取出的状态已经在visited集合中，就没有必要对其进行展开了。❹将展开过一次的状态保存到visited集合中。
next_value(pos, value)返回在pos位置，值为value时所有可能走的路径，其中包括上一次走过的路径。因此需要❺判断是否和上一次走的路径相同。
程序的输出为：
deque简介
在Python中，列表是一个动态的数组，在其尾部添加或删除元素的时间复杂度都是常数，但是在头部添加或删除元素则需要移动列表中所有的元素，因此时间复杂度为O(n)。显然列表只适合作为栈而不适合作为队列。deque是一个双向链表结构，从头部和尾部添加或删除元素的时间复杂度都为常数，但是访问某个下标的元素需要遍历链表，因此访问元素的时间复杂度为O(n)。