潮童街拍

Python 实现递归法解决迷宫问题的示例代码

 更新时间:2020-01-12 19:00:24   作者:佚名   我要评论(0)

迷宫问题
问题描述:
迷宫可用方阵 [m, n] 表示,0 表示可通过,1 表示不能通过。若要求左上角 (0, 0) 进入,设计算法寻求一条能从右下角 (m-1, n-1) 出去的路径。

迷宫问题

问题描述:

潮童街拍迷宫可用方阵 [m, n] 表示,0 表示可通过,1 表示不能通过。若要求左上角 (0, 0) 进入,设计算法寻求一条能从右下角 (m-1, n-1) 出去的路径。

示例图:

期望输出路径图

此示例图基本参数为:

  • m:对应
  • x 轴n:对应 y 轴
  • 绿色线代表期望输出的路径

算法思路

  1. 标记当前所在位置
  2. 如果此时所在位置为终点,说明可以到达终点,退出递归;

否则,则存在 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()

潮童街拍 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

您可能感兴趣的文章:

  • Python基于递归算法实现的走迷宫问题

潮童街拍相关的文章

  • Python 实现递归法解决迷宫问题的示例代码

    Python 实现递归法解决迷宫问题的示例代码

    迷宫问题 问题描述: 迷宫可用方阵 [m, n] 表示,0 表示可通过,1 表示不能通过。若要求左上角 (0, 0) 进入,设计算法寻求一条能从右下角 (m-1, n-1) 出去的路径。
    2020-01-12
  • html2canvas属性和使用方法以及如何使用html2canvas将HTML内容写入Canvas生成图片

    html2canvas属性和使用方法以及如何使用html2canvas将HTML内容写入Canvas生成图片

    如何使用JS截取HTML页面为图片呢,下面为大家介绍一款JS截图插件html2canvas.js html2canvas.js 能够实现在用户浏览器端直接对整个或部分页面进行截屏。 html2can
    2020-01-12
  • golang并发编程的实现

    golang并发编程的实现

    go main函数的执行本身就是一个协程,当使用go关键字的时候,就会创建一个新的协程 channel channel 管道,用于在多个协程之间传递信号 无缓存管道 当对无
    2020-01-12
  • python opencv实现信用卡的数字识别

    python opencv实现信用卡的数字识别

    本项目利用python以及opencv实现信用卡的数字识别 前期准备 导入工具包 定义功能函数 模板图像处理 读取模板图像 cv2.imread(img) 灰度化处理 cv2
    2020-01-12
  • 2019年度web前端面试题总结(主要为Vue面试题)

    2019年度web前端面试题总结(主要为Vue面试题)

    毕业之后就在一直合肥小公司工作,没有老司机、没有技术氛围,在技术的道路上我只能独自摸索。老板也只会画饼充饥,前途一片迷茫看不到任何希望。于是乎,我果断辞
    2020-01-12
  • 深入理解redux之compose的具体应用

    深入理解redux之compose的具体应用

    应用 最近给自己的react项目添加redux的时候,用到了redux中的compose函数,使用compose来增强store,下面是我在项目中的一个应用: import {createStore,apply
    2020-01-12
  • Java使用DateTimeFormatter实现格式化时间

    Java使用DateTimeFormatter实现格式化时间

    用扫描器获取输入的时间(年月日时分),这个时间的格式是常用的格式,然后格式化这个时间,把格式化的时间输出到控制台,可以在控制台重复输入时间.格式化的时间参考企业
    2020-01-12
  • Ranorex通过Python将报告发送到邮箱的方法

    Ranorex通过Python将报告发送到邮箱的方法

    Ranorex测试报告如何发送到邮箱在网上看了下,其实可以通过在Ranorex上或者VS调用编写发送邮箱代码就可以执行发送了,RX主要涉及到的开发语言是C++或者.NET。但是我
    2020-01-12
  • 通过实例解析JMM和Volatile底层原理

    通过实例解析JMM和Volatile底层原理

    这篇文章主要介绍了通过实例解析JMM和Volatile底层原理,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 JMM和
    2020-01-11
  • 浅谈pytorch卷积核大小的设置对全连接神经元的影响

    浅谈pytorch卷积核大小的设置对全连接神经元的影响

    3*3卷积核与2*5卷积核对神经元大小的设置 #这里kerner_size = 2*5 class CONV_NET(torch.nn.Module): #CONV_NET类继承nn.Module类 def __init__(self): super(
    2020-01-11

最新评论

神马电影网www.hmlhsw.com