给一个二维列表,表示迷宫(0表示给出算法,求通道,1表示围墙)。
给出算法,求一条走出迷宫的路径。
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列表,用于计算当前节点在上下左右四个方向的相邻坐标,方便在迷宫中移动探索路径。
三、过程:
1.先建一个栈stack,并将起点坐标(x1,y1)压入栈中。
2.当栈不为空时进入循环,取出栈顶元素作为当前节点curNode。
3.检查当前节点是否为终点,如果是,则说明找到一条从起点到终点的路径,此时,遍历栈并输出路径上的节点坐标,然后返回True。
4.如果当前节点不是终点,就遍历dirs中的四个方向函数,通过调用每个函数计算出下一个节点nextNode的坐标。
5.接着判断下一个节点是否是为可通行的通道(即maze[nextNode[0]][nextNode[1]] == 0),如果是,则将该点压入栈中,表示选择该节点在迷宫中的值标记为2,表示已经走过,然后条出本次对方的遍历,继续下一轮循环去探索,并将该节点在迷宫中标记为2表示已经走过,然后跳出本次对方向的遍历,继续下一轮循环去探索新的节点。
6.如果经过四个方向的遍历,都没有找到可通行的节点,就将当前节点在迷宫中的值标记为2(这里其实已经标记过一次了,可优化去掉重复标记),然后将当前节点从栈中弹出,回退到上一个节点,继续尝试其他方向。
四、最终结果判断:
如果循环结束后栈为空,说明已经尝试了所有可能的路径但都没有找到达终点的路,此时输出“没有路”并返回False。
代码:
代码解析:
1.定义maze和用于计算相邻节点坐标的方向函数列表dirs。
2.maze_path函数接受起点坐标(x1,y1)和终点坐标(x2,y2)作为参数。
3.先创建空栈stack并将起点坐标压入栈中。然后在循环中,不断取出栈顶袁术作为当前节点curNode,并检查是否到达终点,如果到达则输出路径并返回True。
4.这里遍历dirs中的方向函数,通过调佣函数得到下一个节点nextNode的坐标。然后判断下一个节点是否可通行,如果可以就将其压入栈中,并在迷宫中标记为2,表示已走过,然后跳出本次方向遍历,继续探索新节点。
5.如果对四个方向遍历完都没有找到可通行节点,就先在迷宫中再次标记当前尝试的下一个节点为2(可优化去掉这一步,因为前面找到可通行节点时已经标记过了),然后将当前节点从栈中弹出,回退到上一个节点。如果循环结束栈为空,就输出“没有路”并返回False,表示没有找到从起点到终点的路径。