|
首先自定义一个二维数组
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]
0：表示路
1：表示墙体
一.深度优先搜索+回溯（使用栈来存储已走过的路径）
1,定义四个lambda表达式作为右左下上四个方向。
2.从初始结点开始，当下一个结点可以走的时候，自己的坐标点入栈。并标记为已经走过。
3.当没有下一个结点可以走的时候，出栈，说明此路不通。回溯到可以有下一个结点可以走的结点处。重新开始步骤2.
4.当找到目标结点的时候，遍历栈中的元素，即为一条可以走通的路。不一定是最优的路线规划。
#使用栈来存储路径
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):
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)
return True
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[nextNode[0]][nextNode[1]] = 2
stack.pop()
else:
print("没有路")
return False
maze_path(1,1,8,8)
二.广度优先算法（使用队列来储存已经走过的路线）
1.定义四个lambda表达式作为右左下上四个方向。
2..从初始结点开始，如果有一个节点可以走的时候，自己的坐标点+自己的上一个结点入队列，并表示为已经走过。
3.只要队列中铀元素就把步骤2的队列中的元素出队列存放在数组path中。
4.当找到目标结点的时候，结束查找。如果找不到目标结点，即没有一条路可以到达。
5.通过path数组中第三项元素指向的位置，逆序打印path中前两项元素，即为最后的路线。一定时最优的路线。
from collections import deque
#使用队列
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 print_r(path):
curNode = path[-1]
print(curNode)
realpath=[]
while curNode[2] != -1:
realpath.append(curNode[0:2])
curNode = path[curNode[2]]
realpath.append(curNode[0:2]) # 起点
realpath.reverse()
for node in realpath:
print(node)
def maze_path_queue(x1, y1, x2, y2):
queue = deque()
queue.append((x1, y1, -1)) #起点
path = []
while len(queue) > 0: #只要队不为空
curNode = queue.pop() #队首出队
path.append(curNode)
if curNode[0] == x2 and curNode[1] == y2:
print_r(path)
return True
for dir in dirs:
nextNode = dir(curNode[0], curNode[1]) #下一个节点
if maze[nextNode[0]][nextNode[1]] == 0:
queue.append((nextNode[0], nextNode[1], len(path) - 1)) # 后续节点进队，记录哪个结点带她来的
maze[nextNode[0]][nextNode[1]] = 2 # 标记已经走过
else:
print("没有路")
return False
maze_path_queue(1,1,8,8)
|