Python 实现递归法解决迷宫问题的示例代码
迷宫可用方阵[m,n]表示，0表示可通过，1表示不能通过。若要求左上角(0,0)进入，设计算法寻求一条能从右下角(m-1,n-1)出去的路径。
示例图：
- m：对应
- x轴n：对应y轴
- 绿色线代表期望输出的路径
算法思路
- 标记当前所在位置
- 如果此时所在位置为终点，说明可以到达终点，退出递归；
否则，则存在4种可能的移动方向即上、下、左、右，遍历这4个方向，如果这4个方向存在相邻值为0的点，则将当前点坐标标记为该相邻值为0的点坐标，进入递归
直观理解为：
上图中红色圈的相邻值为0的点有3个，则会依次遍历这3个点寻求某一条件并进入递归
实现过程
标记函数
defmark(maze,pos): """ 标记函数，用来标记历史走过的位置 :parammaze:一个m*n大小的二维矩阵迷宫 :parampos:当前需要标记的位置坐标pos=(x,y)，x=pos[0],y=pos[1] """ maze[pos[0]][pos[1]]=2#将走过的位置标记为2
移动函数
defmove(maze,pos): """ 移动函数，用来测试当前位置是否可继续移动，移动条件为当前位置为0 :parammaze:一个m*n大小的二维矩阵迷宫 :parampos:当前需要标记的位置坐标pos=(x,y)，x=pos[0],y=pos[1] :return:bool类型 """ returnmaze[pos[0]][pos[1]]==0
核心函数-路径查找函数
deffind_path(maze,start,end): """ 路径查找函数 :parammaze:一个m*n大小的二维矩阵迷宫 :paramstart:起始点位置坐标，start=(1,1) :paramend:终点坐标，end=(m,n) :return:bool类型 """ mark(maze,start)#将起始位置标记 ifstart==end:#路径查找（递归）终止条件为到达终点 move_path.append(start) returnTrue #未到达终点时，存在4种可能的移动方向，即上(-1,0)，下(1,0)，左(0,-1)，右(0,1) move_direction=[ (-1,0),(1,0),(0,-1),(0,1) ] direction=['↑','↓','←','→'] foriinrange(4):#遍历4种可能的方向 next_start=(start[0]+move_direction[i][0],start[1]+move_direction[i][1])#下一个可能的起始点坐标 ifmove(maze,next_start):#找出存在0即可移动的下一个起始点坐标，进入递归 iffind_path(maze,next_start,end): #这里之所以仍然添加起始点坐标是因为当查询到下一个位置就是终点或者可到达终点时记录此时位置 move_path.append(start) path_direction.append(direction[i])#记录路径方向 returnTrue returnFalse#遍历递归了4种可能方向后仍不能到达终点则说明无法走出迷宫
算法到这里基本上已经算完成，整体上不算太复杂
美化输出
生成带有移动路径数据的迷宫矩阵
defpath_maze(maze,directions_map): """ 生成带有移动路径的迷宫矩阵 :parammaze:一个m*n大小的二维矩阵迷宫 :paramdirections_map:一个记录移动方向坐标的字典，有↑，↓，←，→4个元素 :return:path_maze """ n,m=len(maze[0]),len(maze) forxinrange(1,m-1): foryinrange(1,n-1): maze[x][y]=maze[x][y]ifmaze[x][y]!=2else0#将标记的2还原为0 forxinrange(m): foriinrange(1,2*n-1,2): maze[x].insert(i,'')#重初始化maze，在每两个元素间插入占位符''3个空格 forxinrange(1,2*m-1,2): maze.insert(x,['','']*(n-1)+[''])#插入两种空格占位符''和'' fordirectionindirections_map: fordirections_positionindirections_map[direction]: i,j=directions_position i=2*i j=2*j ifdirection=="↑": maze[i-1][j]="↑" ifdirection=="↓": maze[i+1][j]="↓" ifdirection=="←": maze[i][j]="←" ifdirection=="→": maze[i][j+1]="→" returnmaze
生成的带路径数据的迷宫矩阵部分数据截图如下：
美化打印迷宫矩阵
defprint_maze(maze,text='原始迷宫为：',end1='',end2='\n\n',xs=0,xe=0,ys=0,ye=0): """ 输出迷宫矩阵，非必要，可注释删除 :parammaze:一个m*n大小的二维矩阵迷宫 :paramtext:输出提示 :paramend1:控制每行尾结束符 :paramend2:控制每行尾结束符 :paramxs:控制是否输出最上方的1环，0为输出，1为不输出 :paramxe:控制是否输出最上方的1环，0为输出，1为不输出 :paramys:控制是否输出最上方的1环，0为输出，1为不输出 :paramye:控制是否输出最上方的1环，0为输出，1为不输出 """ print(text) n,m=len(maze[0]),len(maze) forxinrange(xs,m-xe): foryinrange(ys,n-ye): print(maze[x][y],end=end1) print(end=end2)
最终输出结果：
效果尚可
完整代码
#-*-coding:utf-8-*-
"""
Createdon2020/1/1110:51
Author:zxt
File:maze_recursion.py
Software:PyCharm
"""
fromrandomimportrandint
defmark(maze,pos):
"""
标记函数，用来标记历史走过的位置
:parammaze:一个m*n大小的二维矩阵迷宫
:parampos:当前需要标记的位置坐标pos=(x,y)，x=pos[0],y=pos[1]
"""
maze[pos[0]][pos[1]]=2#将走过的位置标记为2
defmove(maze,pos):
"""
移动函数，用来测试当前位置是否可继续移动，移动条件为当前位置为0
:parammaze:一个m*n大小的二维矩阵迷宫
:parampos:当前需要标记的位置坐标pos=(x,y)，x=pos[0],y=pos[1]
:return:bool类型
"""
returnmaze[pos[0]][pos[1]]==0
move_path=[]#记录能成功到达出口的移动路径坐标
path_direction=[]#记录能成功到达出口的移动路径方向
deffind_path(maze,start,end):
"""
路径查找函数
:parammaze:一个m*n大小的二维矩阵迷宫
:paramstart:起始点位置坐标，start=(1,1)
:paramend:终点坐标，end=(m,n)
:return:bool类型
"""
mark(maze,start)#将起始位置标记
ifstart==end:#路径查找（递归）终止条件为到达终点
move_path.append(start)
returnTrue
#未到达终点时，存在4种可能的移动方向，即上(-1,0)，下(1,0)，左(0,-1)，右(0,1)
move_direction=[
(-1,0),(1,0),(0,-1),(0,1)
]
direction=['↑','↓','←','→']
foriinrange(4):#遍历4种可能的方向
next_start=(start[0]+move_direction[i][0],start[1]+move_direction[i][1])#下一个可能的起始点坐标
ifmove(maze,next_start):#找出存在0即可移动的下一个起始点坐标，进入递归
iffind_path(maze,next_start,end):
#这里之所以仍然添加起始点坐标是因为当查询到下一个位置就是终点或者可到达终点时记录此时位置
move_path.append(start)
path_direction.append(direction[i])#记录路径方向
returnTrue
returnFalse#遍历递归了4种可能方向后仍不能到达终点则说明无法走出迷宫
defgen_maze(m,n):
"""
生成随机迷宫阵列
:paramm:int类型
:paramn:int类型
:return:maze
"""
m+=2
n+=2#m和n均+2是为了构造最外层的1
maze=[[1foriinrange(n)]forjinrange(m)]#初始化大小为m*n，值全为1的二维矩阵
forxinrange(1,m-1):
foryinrange(1,n-1):
"""
这里x,y取值范围为x∈[1,m-1)，y∈[1,n-1)是因为我们令此迷宫的最外层（四周）均为1，如：
考察3*3矩阵，一种可能的阵列为：
[
_|←---n:y---→|
↑[1,1,1,1,1],
|[1,0,1,0,1],
m:x[1,0,0,1,1],
|[1,1,0,0,1],
↓[1,1,1,1,1]
]
"""
if(x==1andy==1)or(x==m-2andy==n-2):
maze[x][y]=0#起始点和终点必为0
else:
maze[x][y]=randint(0,1)#在最外层均为1的情况下内部随机取0，1
returnmaze
defprint_maze(maze,text='原始迷宫为：',end1='',end2='\n\n',xs=0,xe=0,ys=0,ye=0):
"""
输出迷宫矩阵，非必要，可注释删除
:parammaze:一个m*n大小的二维矩阵迷宫
:paramtext:输出提示
:paramend1:控制每行尾结束符
:paramend2:控制每行尾结束符
:paramxs:控制是否输出最上方的1环，0为输出，1为不输出
:paramxe:控制是否输出最上方的1环，0为输出，1为不输出
:paramys:控制是否输出最上方的1环，0为输出，1为不输出
:paramye:控制是否输出最上方的1环，0为输出，1为不输出
"""
print(text)
n,m=len(maze[0]),len(maze)
forxinrange(xs,m-xe):
foryinrange(ys,n-ye):
print(maze[x][y],end=end1)
print(end=end2)
defpath_maze(maze,directions_map):
"""
生成带有移动路径的迷宫矩阵
:parammaze:一个m*n大小的二维矩阵迷宫
:paramdirections_map:一个记录移动方向坐标的字典，有↑，↓，←，→4个元素
:return:path_maze
"""
n,m=len(maze[0]),len(maze)
forxinrange(1,m-1):
foryinrange(1,n-1):
maze[x][y]=maze[x][y]ifmaze[x][y]!=2else0#将标记的2还原为0
forxinrange(m):
foriinrange(1,2*n-1,2):
maze[x].insert(i,'')#重初始化maze，在每两个元素间插入占位符''3个空格
forxinrange(1,2*m-1,2):
maze.insert(x,['','']*(n-1)+[''])#插入两种空格占位符''和''
fordirectionindirections_map:
fordirections_positionindirections_map[direction]:
i,j=directions_position
i=2*i
j=2*j
ifdirection=="↑":
maze[i-1][j]="↑"
ifdirection=="↓":
maze[i+1][j]="↓"
ifdirection=="←":
maze[i][j]="←"
ifdirection=="→":
maze[i][j+1]="→"
returnmaze
defmain():
#maze=gen_maze(m=10,n=12)
maze=\
[
[1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,1,1,0,0,0,1,0,0,0,1],
[1,0,1,0,0,0,0,1,0,1,0,1,0,1],
[1,0,1,0,1,1,1,1,0,1,0,1,0,1],
[1,0,1,0,0,0,0,0,0,1,1,1,0,1],
[1,0,1,1,1,1,1,1,1,1,0,0,0,1],
[1,0,1,0,0,0,0,0,0,0,0,1,0,1],
[1,0,0,0,1,1,1,0,1,0,1,1,0,1],
[1,0,1,0,1,0,1,0,1,0,1,0,0,1],
[1,0,1,0,1,0,1,0,1,1,1,1,0,1],
[1,0,1,0,0,0,1,0,0,1,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1]
]#输入样式矩阵，这里最外层用1环包围住，目的是方便后续的处理，可以用gen_maze()函数自生成
print_maze(maze)
iffind_path(maze,start=(1,1),end=(10,12)):
mp=move_path[::-1]
pd=path_direction[::-1]
#这里pos[0]和pos[1]都要-1是因为原来的递归计算中存在最外层的1环
print('坐标移动顺序为:',[(pos[0]-1,pos[1]-1)forposinmp])
path_direction_map={
'↑':[],
'↓':[],
'←':[],
'→':[]
}#路径方向的映射表
foriinrange(len(pd)):
path_direction_map[pd[i]].append(mp[i])
maze=path_maze(maze,path_direction_map)
print_maze(maze,text='迷宫移动路径为：',end1='',end2='\n',xs=1,xe=1,ys=1,ye=1)
else:
print('此迷宫无解')
if__name__=='__main__':
main()
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。