# 用栈、回溯算法设计迷宫程序

2、迷宫设计栈扮演的角色

## 3、Python实现走迷宫

```# ch11_1.py
from pprint import pprint
maze = [                                    # 迷宫地图
[1, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 1, 1],
[1, 0, 1, 0, 0, 1],
[1, 0, 0, 0, 1, 1],
[1, 0, 1, 0, 0, 1],
[1, 1, 1, 1, 1, 1]
]
directions = [                              # 使用列表设计走迷宫方向
lambda x, y: (x-1, y),        # 往上走
lambda x, y: (x+1, y),        # 往下走
lambda x, y: (x, y-1),        # 往左走
lambda x, y: (x, y+1),        # 往右走
]
def maze_solve(x, y, goal_x, goal_y):
''' 解迷宫程序 x, y是迷宫入口, goal_x, goal_y是迷宫出口'''
maze[x][y] = 2
stack = []                              # 建立路径栈
stack.append((x, y))                    # 将路径push入栈
print('迷宫开始')
while (len(stack) > 0):
cur = stack[-1]                     # 目前位置
if cur[0] == goal_x and cur[1] == goal_y:
print('抵达出口')
return True                     # 抵达出口返回True
for dir in directions:              # 依上, 下, 左, 右优先次序走此迷宫
next = dir(cur[0], cur[1])
if maze[next[0]][next[1]] == 0: # 如果是通道可以走
stack.append(next)
maze[next[0]][next[1]] = 2  # 用2标记走过的路
break
else:                               # 如果进入死路, 则回溯
maze[cur[0]][cur[1]] = 3        # 标记死路
stack.pop()                     # 回溯
else:
print("没有路径")
return False
maze_solve(1, 1, 4, 4)
pprint(maze)                                # 跳行显示元素