DDR爱好者之家 Design By 杰米
迷宫问题
问题描述：
迷宫可用方阵 [m, n] 表示，0 表示可通过，1 表示不能通过。若要求左上角 (0, 0) 进入，设计算法寻求一条能从右下角 (m-1, n-1) 出去的路径。
示例图：
此示例图基本参数为：
- m：对应
- x 轴n：对应 y 轴
- 绿色线代表期望输出的路径
算法思路
- 标记当前所在位置
- 如果此时所在位置为终点，说明可以到达终点，退出递归；
否则，则存在 4 种可能的移动方向即上、下、左、右，遍历这 4 个方向，如果这 4 个方向存在相邻值为 0 的点，则将当前点坐标标记为该相邻值为 0 的点坐标，进入递归
直观理解为：
上图中红色圈的相邻值为 0 的点有 3 个，则会依次遍历这 3 个点寻求某一条件并进入递归
实现过程
标记函数
def mark(maze, pos): """ 标记函数，用来标记历史走过的位置 :param maze: 一个 m*n 大小的二维矩阵迷宫 :param pos: 当前需要标记的位置坐标 pos = (x, y)，x = pos[0], y = pos[1] """ maze[pos[0]][pos[1]] = 2 # 将走过的位置标记为 2
移动函数
def move(maze, pos): """ 移动函数，用来测试当前位置是否可继续移动，移动条件为当前位置为 0 :param maze: 一个 m*n 大小的二维矩阵迷宫 :param pos: 当前需要标记的位置坐标 pos = (x, y)，x = pos[0], y = pos[1] :return: bool 类型 """ return maze[pos[0]][pos[1]] == 0
核心函数 - 路径查找函数
def find_path(maze, start, end):
"""
路径查找函数
:param maze: 一个 m*n 大小的二维矩阵迷宫
:param start: 起始点位置坐标，start = (1, 1)
:param end: 终点坐标，end = (m, n)
:return: bool 类型
"""
mark(maze, start) # 将起始位置标记
if start == end: # 路径查找（递归）终止条件为到达终点
move_path.append(start)
return True
# 未到达终点时，存在 4 种可能的移动方向，即上 (-1, 0)，下 (1, 0)，左 (0, -1)，右 (0, 1)
move_direction = [
(-1, 0), (1, 0), (0, -1), (0, 1)
]
direction = ['↑', '↓', '←', '→']
for i in range(4): # 遍历 4 种可能的方向
next_start = (start[0] + move_direction[i][0], start[1] + move_direction[i][1]) # 下一个可能的起始点坐标
if move(maze, next_start): # 找出存在 0 即可移动的下一个起始点坐标，进入递归
if find_path(maze, next_start, end):
# 这里之所以仍然添加起始点坐标是因为当查询到下一个位置就是终点或者可到达终点时记录此时位置
move_path.append(start)
path_direction.append(direction[i]) # 记录路径方向
return True
return False # 遍历递归了 4 种可能方向后仍不能到达终点则说明无法走出迷宫
算法到这里基本上已经算完成，整体上不算太复杂
美化输出
生成带有移动路径数据的迷宫矩阵
def path_maze(maze, directions_map):
"""
生成带有移动路径的迷宫矩阵
:param maze: 一个 m*n 大小的二维矩阵迷宫
:param directions_map: 一个记录移动方向坐标的字典，有 ↑，↓，←，→ 4 个元素
:return: path_maze
"""
n, m = len(maze[0]), len(maze)
for x in range(1, m-1):
for y in range(1, n-1):
maze[x][y] = maze[x][y] if maze[x][y] != 2 else 0 # 将标记的 2 还原为 0
for x in range(m):
for i in range(1, 2 * n - 1, 2):
maze[x].insert(i, ' ') # 重初始化 maze，在每两个元素间插入占位符 ' ' 3 个空格
for x in range(1, 2 * m - 1, 2):
maze.insert(x, [' ', ' '] * (n-1) + ['']) # 插入两种空格占位符 ' ' 和 ' '
for direction in directions_map:
for directions_position in directions_map[direction]:
i, j = directions_position
i = 2 * i
j = 2 * j
if direction == "↑":
maze[i - 1][j] = "↑"
if direction == "↓":
maze[i + 1][j] = "↓"
if direction == "←":
maze[i][j] = " ← "
if direction == "→":
maze[i][j + 1] = " → "
return maze
生成的带路径数据的迷宫矩阵部分数据截图如下：
美化打印迷宫矩阵
def print_maze(maze, text='原始迷宫为：', end1=' ', end2='\n\n', xs=0, xe=0, ys=0, ye=0):
"""
输出迷宫矩阵，非必要，可注释删除
:param maze: 一个 m*n 大小的二维矩阵迷宫
:param text: 输出提示
:param end1: 控制每行尾结束符
:param end2: 控制每行尾结束符
:param xs: 控制是否输出最上方的 1 环，0 为输出，1 为不输出
:param xe: 控制是否输出最上方的 1 环，0 为输出，1 为不输出
:param ys: 控制是否输出最上方的 1 环，0 为输出，1 为不输出
:param ye: 控制是否输出最上方的 1 环，0 为输出，1 为不输出
"""
print(text)
n, m = len(maze[0]), len(maze)
for x in range(xs, m-xe):
for y in range(ys, n-ye):
print(maze[x][y], end=end1)
print(end=end2)
最终输出结果：
效果尚可
完整代码
# -*- coding: utf-8 -*-
"""
Created on 2020/1/11 10:51
Author : zxt
File : maze_recursion.py
Software: PyCharm
"""
from random import randint
def mark(maze, pos):
"""
标记函数，用来标记历史走过的位置
:param maze: 一个 m*n 大小的二维矩阵迷宫
:param pos: 当前需要标记的位置坐标 pos = (x, y)，x = pos[0], y = pos[1]
"""
maze[pos[0]][pos[1]] = 2 # 将走过的位置标记为 2
def move(maze, pos):
"""
移动函数，用来测试当前位置是否可继续移动，移动条件为当前位置为 0
:param maze: 一个 m*n 大小的二维矩阵迷宫
:param pos: 当前需要标记的位置坐标 pos = (x, y)，x = pos[0], y = pos[1]
:return: bool 类型
"""
return maze[pos[0]][pos[1]] == 0
move_path = [] # 记录能成功到达出口的移动路径坐标
path_direction = [] # 记录能成功到达出口的移动路径方向
def find_path(maze, start, end):
"""
路径查找函数
:param maze: 一个 m*n 大小的二维矩阵迷宫
:param start: 起始点位置坐标，start = (1, 1)
:param end: 终点坐标，end = (m, n)
:return: bool 类型
"""
mark(maze, start) # 将起始位置标记
if start == end: # 路径查找（递归）终止条件为到达终点
move_path.append(start)
return True
# 未到达终点时，存在 4 种可能的移动方向，即上 (-1, 0)，下 (1, 0)，左 (0, -1)，右 (0, 1)
move_direction = [
(-1, 0), (1, 0), (0, -1), (0, 1)
]
direction = ['↑', '↓', '←', '→']
for i in range(4): # 遍历 4 种可能的方向
next_start = (start[0] + move_direction[i][0], start[1] + move_direction[i][1]) # 下一个可能的起始点坐标
if move(maze, next_start): # 找出存在 0 即可移动的下一个起始点坐标，进入递归
if find_path(maze, next_start, end):
# 这里之所以仍然添加起始点坐标是因为当查询到下一个位置就是终点或者可到达终点时记录此时位置
move_path.append(start)
path_direction.append(direction[i]) # 记录路径方向
return True
return False # 遍历递归了 4 种可能方向后仍不能到达终点则说明无法走出迷宫
def gen_maze(m, n):
"""
生成随机迷宫阵列
:param m: int 类型
:param n: int 类型
:return: maze
"""
m += 2
n += 2 # m 和 n 均 +2 是为了构造最外层的 1
maze = [[1 for i in range(n)] for j in range(m)] # 初始化大小为 m * n，值全为 1 的二维矩阵
for x in range(1, m-1):
for y in range(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 == 1 and y == 1) or (x == m - 2 and y == n - 2):
maze[x][y] = 0 # 起始点和终点必为 0
else:
maze[x][y] = randint(0, 1) # 在最外层均为 1 的情况下内部随机取 0，1
return maze
def print_maze(maze, text='原始迷宫为：', end1=' ', end2='\n\n', xs=0, xe=0, ys=0, ye=0):
"""
输出迷宫矩阵，非必要，可注释删除
:param maze: 一个 m*n 大小的二维矩阵迷宫
:param text: 输出提示
:param end1: 控制每行尾结束符
:param end2: 控制每行尾结束符
:param xs: 控制是否输出最上方的 1 环，0 为输出，1 为不输出
:param xe: 控制是否输出最上方的 1 环，0 为输出，1 为不输出
:param ys: 控制是否输出最上方的 1 环，0 为输出，1 为不输出
:param ye: 控制是否输出最上方的 1 环，0 为输出，1 为不输出
"""
print(text)
n, m = len(maze[0]), len(maze)
for x in range(xs, m-xe):
for y in range(ys, n-ye):
print(maze[x][y], end=end1)
print(end=end2)
def path_maze(maze, directions_map):
"""
生成带有移动路径的迷宫矩阵
:param maze: 一个 m*n 大小的二维矩阵迷宫
:param directions_map: 一个记录移动方向坐标的字典，有 ↑，↓，←，→ 4 个元素
:return: path_maze
"""
n, m = len(maze[0]), len(maze)
for x in range(1, m-1):
for y in range(1, n-1):
maze[x][y] = maze[x][y] if maze[x][y] != 2 else 0 # 将标记的 2 还原为 0
for x in range(m):
for i in range(1, 2 * n - 1, 2):
maze[x].insert(i, ' ') # 重初始化 maze，在每两个元素间插入占位符 ' ' 3 个空格
for x in range(1, 2 * m - 1, 2):
maze.insert(x, [' ', ' '] * (n-1) + ['']) # 插入两种空格占位符 ' ' 和 ' '
for direction in directions_map:
for directions_position in directions_map[direction]:
i, j = directions_position
i = 2 * i
j = 2 * j
if direction == "↑":
maze[i - 1][j] = "↑"
if direction == "↓":
maze[i + 1][j] = "↓"
if direction == "←":
maze[i][j] = " ← "
if direction == "→":
maze[i][j + 1] = " → "
return maze
def main():
# 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)
if find_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) for pos in mp])
path_direction_map = {
'↑': [],
'↓': [],
'←': [],
'→': []
} # 路径方向的映射表
for i in range(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()
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
DDR爱好者之家 Design By 杰米
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
DDR爱好者之家 Design By 杰米
暂无评论...
更新日志
2024年11月25日
2024年11月25日
- 凤飞飞《我们的主题曲》飞跃制作[正版原抓WAV+CUE]
- 刘嘉亮《亮情歌2》[WAV+CUE][1G]
- 红馆40·谭咏麟《歌者恋歌浓情30年演唱会》3CD[低速原抓WAV+CUE][1.8G]
- 刘纬武《睡眠宝宝竖琴童谣 吉卜力工作室 白噪音安抚》[320K/MP3][193.25MB]
- 【轻音乐】曼托凡尼乐团《精选辑》2CD.1998[FLAC+CUE整轨]
- 邝美云《心中有爱》1989年香港DMIJP版1MTO东芝首版[WAV+CUE]
- 群星《情叹-发烧女声DSD》天籁女声发烧碟[WAV+CUE]
- 刘纬武《睡眠宝宝竖琴童谣 吉卜力工作室 白噪音安抚》[FLAC/分轨][748.03MB]
- 理想混蛋《Origin Sessions》[320K/MP3][37.47MB]
- 公馆青少年《我其实一点都不酷》[320K/MP3][78.78MB]
- 群星《情叹-发烧男声DSD》最值得珍藏的完美男声[WAV+CUE]
- 群星《国韵飘香·贵妃醉酒HQCD黑胶王》2CD[WAV]
- 卫兰《DAUGHTER》【低速原抓WAV+CUE】
- 公馆青少年《我其实一点都不酷》[FLAC/分轨][398.22MB]
- ZWEI《迟暮的花 (Explicit)》[320K/MP3][57.16MB]