给一个二维数组列表，表示迷宫。0表示通道，1表示围墙。给出算法，求一条走出迷宫的路径。
如下图：
代码如下：
# coding: utf-8 # 迷宫问题使用栈来实现 # 定义迷宫 1：表示墙 0：表示路 maze = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 1, 0, 0, 0, 1, 0, 1], [1, 0, 0, 1, 0, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 1, 1, 0, 0, 1], [1, 0, 1, 1, 1, 0, 0, 0, 0, 1], [1, 0, 0, 0, 1, 0, 0, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1, 0, 0, 1], [1, 0, 1, 1, 1, 0, 1, 1, 0, 1], [1, 1, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ] # 定义四个方向 下、右、上、左。每一步都要检查4个方向，按下、右、上、左顺序，判断那个方向可以走 dirs = [ lambda x, y: (x + 1, y), # 下 lambda x, y: (x, y + 1), # 右 lambda x, y: (x - 1, y), # 上 lambda x, y: (x, y - 1), # 左 ] # x1,y1表示迷宫入口的坐标，x2,y2表示迷宫出口坐标 def mgpath(x1, y1, x2, y2): # 声明一个栈 stack = [] # 走过的路的坐标都要加到栈里，下面先把第一步也就是入口坐标加到栈里 stack.append((x1, y1)) # 栈不空时循环。栈空时表示没有出口，无路可走 while len(stack) > 0: # 查看栈顶元素 curNode = stack[-1] if curNode[0] == x2 and curNode[1] == y2: # 表示到达终点 for p in stack: # 打印所走路径坐标 print p break # 判断栈顶元素，也就是当前坐标的哪个方向可以走 for dir in dirs: # 获取四个方向的坐标 *curNode 打散元组，传给匿名函数 nextNode = dir(*curNode) # 找到了下一个方块，也就是路 if maze[nextNode[0]][nextNode[1]] == 0: # 将路的坐标放到栈里面 stack.append(nextNode) # 标记为已经走过的路，防止死循环 maze[nextNode[0]][nextNode[1]] = -1 # 根据下、右、上、左顺序，找到路就break break else: # 4个方向都没有路 maze[curNode[0]][curNode[1]] = -1 # 回退一格 stack.pop() return False mgpath(1,1,8,8)
结束！