迷宫问题求解

maze.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import Queue

"""

Problem:(from http://weibo.com/lirenchen)

从图左边入口处的2011进去，在迷宫里转悠，最后变成2012从右边出来。可以在迷宫里转圈，
可以重复之前走过的路，但不能回退。


      +-----+-----+-----+     +-----+-----+-----+
      |       +7        |     |       x3        |     
  +---+     +-----+     +-----+     +-----+     +---+
2011 ->     |     |                 |     |       -> 2012   
  +---+     +-----+     +-----+     +-----+     +---+
      |       /2        |     |       -5        |
      +-----+-----+-----+     +-----+-----+-----+

根据题意:
The first move[+7], the last move[-5]:

     [+7]       ...       [-5]
2011----->2018 ---->  2017---->2012

以2018为根节点，可以构造一个树形结构，然后逐层遍历（广度优先），直到找到
一个子孙为2017的节点。

"""
# 定义节点类
class Node(object):
    """
    num: 节点的值
    parent: 父节点, 根节点次值设为None
    path: 父节点到该节点的路径
    """
    def __init__(self, num, parent, path):
        self.num = num
        self.parent = parent
        self.path=path

# 自下而上打印节点()，just for debug
def print_nodes(tail):
    if tail != None:
        print_nodes(tail.parent)
        print tail.path, tail.num

# 打印结果
def solution(tail):
    ops = []
    solution='2011'
    while tail != None:
        ops.append(tail.path)
        tail = tail.parent
    ops.reverse()
    solution += ' '.join(ops)
    print solution
        
# 广度优先搜索
def bfs(node):
    queue = Queue.Queue()
    explored = set()
    queue.put(node)
    while not queue.empty():
        front = queue.get()
        num = front.num

        if num not in explored:
            explored.add(num)
            if num == 2017:
                print "Found solution: "
                solution(front)
                #print_nodes(front)  
                print "-5 =2012"
                break
            else:                      #根据num的基偶性构造孩子
                if num % 2 == 1:
                    newNum = (num + 7)/2
                    next = Node(newNum, front, "+7/2")
                    queue.put(next)
                if num % 2 == 0:
                    newNum = (num/2) + 7
                    next = Node(newNum, front, "/2+7")
                    queue.put(next)
                #将另外两个孩子节点加入队列
                queue.put(Node((num*3-5), front, "*3-5"))
                queue.put(Node((num-5)*3, front, "-5*3"))

if __name__ == '__main__':
    root = Node(2018, None, " +7")
    bfs(root)

    

result.md

结果截图：