![算法:栈与队列的经典案例,模拟迷宫算法 算法:栈与队列的经典案例,模拟迷宫算法](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzY3NC84MGYyYTQ0ZDUyN2RjMDQzZTMzN2I4MDQ3NTMyNmRlMi5wbmc=)
模拟迷宫
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]
]
栈思路 == 深度优先搜索
dirs = [
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_path(x1, y1, x2, y2):
"""x1起点 x2终点"""
stack = [(x1, y1)]
while len(stack) > 0:
curNode = stack[-1]
if curNode[0] == x2 and curNode[1] == y2:
print('找到迷宫出路')
for p in stack:
print(p)
break
for di in dirs:
nextNode = di(curNode[0], curNode[1])
if maze[nextNode[0]][nextNode[1]] == 0:
stack.append(nextNode)
maze[nextNode[0]][nextNode[1]] = 2
break
else:
maze[curNode[0]][curNode[1]] = 2
stack.pop()
else:
print('该迷宫没有出路')
return False
maze_path(1, 1, 8, 8)
队列思路 == 深度优先搜索
from collections import deque
dirs = [
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 print_r(path):
real_path = []
i = len(path) - 1
while i >= 0:
real_path.append(path[i][0:2])
i = path[i][2]
real_path.reverse()
for node in real_path:
print(node)
def maze_path_queue(x1, y1, x2, y2):
queue = deque()
path = []
queue.append((x1, y1, -1))
while len(queue) > 0:
cur_Node = queue.popleft()
path.append(cur_Node)
if cur_Node[0] == x2 and cur_Node[1] == y2:
print('找到迷宫出路')
print_r(path)
return True
for di in dirs:
next_node = di(cur_Node[0], cur_Node[1])
if maze[next_node[0]][next_node[1]] == 0:
queue.append((next_node[0], next_node[1], len(path) - 1))
maze[next_node[0]][next_node[1]] = 2
return False
maze_path_queue(1, 1, 8, 8)