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

迷宫问题

问题描述:

迷宫可用方阵 [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()

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

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

    本文实例讲述了Python基于递归算法实现的走迷宫问题.分享给大家供大家参考,具体如下: 什么是递归? 简单地理解就是函数调用自身的过程就称之为递归. 什么时候用到递归? 如果一个问题可以表示为更小规模的迭代运算,就可以使用递归算法. 迷宫问题:一个由0或1构成的二维数组中,假设1是可以移动到的点,0是不能移动到的点,如何从数组中间一个值为1的点出发,每一只能朝上下左右四个方向移动一个单位,当移动到二维数组的边缘,即可得到问题的解,类似的问题都可以称为迷宫问题. 在python中可以使用list

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

    迷宫问题 问题描述: 迷宫可用方阵 [m, n] 表示,0 表示可通过,1 表示不能通过.若要求左上角 (0, 0) 进入,设计算法寻求一条能从右下角 (m-1, n-1) 出去的路径. 示例图: 此示例图基本参数为: m:对应 x 轴n:对应 y 轴 绿色线代表期望输出的路径 算法思路 标记当前所在位置 如果此时所在位置为终点,说明可以到达终点,退出递归: 否则,则存在 4 种可能的移动方向即上.下.左.右,遍历这 4 个方向,如果这 4 个方向存在相邻值为 0 的点,则将当前点坐标标记为该相

  • Python基于回溯法解决01背包问题实例

    本文实例讲述了Python基于回溯法解决01背包问题.分享给大家供大家参考,具体如下: 同样的01背包问题,前面采用动态规划的方法,现在用回溯法解决.回溯法采用深度优先策略搜索问题的解,不多说,代码如下: bestV=0 curW=0 curV=0 bestx=None def backtrack(i): global bestV,curW,curV,x,bestx if i>=n: if bestV<curV: bestV=curV bestx=x[:] else: if curW+w[i]

  • Java数据结构BFS广搜法解决迷宫问题

    目录 1.例题 题目描述 输入 输出 测试数据  2. 思路分析 基本思想 具体步骤 代码实现 3.BFS小结 求解思路: 注意 1.例题 题目描述 迷宫由 n 行 m 列的单元格组成,每个单元格要么是空地,要么是障碍物.其中1表示空地,可以走通,2表示障碍物.给定起点坐标startx,starty以及终点坐标endx,endy.现请你找到一条从起点到终点的最短路径长度. 输入 第一行包含两个整数n,m(1<=n,m<=1000).接下来 n 行,每行包含m个整数(值1或2),用于表示这个二维

  • python编程冒泡排序法实现动图排序示例解析

    目录 先上个冒泡排序的效果图: 动态排序的原理 Python tkinter库Canvas操作 动态排序的完整代码 部分代码注释 先上个冒泡排序的效果图: 是不是,有那么一点点像了? 其实要做这个动图真不是很难,来看冒泡的代码: >>> def Bubble(List): L = len(List)-1 for i in range(L): for j in range(L-i): if List[j]>List[j+1]: List[j],List[j+1]=List[j+1],

  • python实现合并两个有序列表的示例代码

    题目描述 将两个升序链表合并为一个新的升序链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的. LeetCode原题地址:https://leetcode-cn.com/problems/merge-two-sorted-lists/ 测试用例 示例1 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例2 输入:l1 = [], l2 = [] 输出:[] 示例3 输入:l1 = [], l2 = [0] 输出:[0] 代码详解 因为Lee

  • Python批量解压&压缩文件夹的示例代码

    目录 一.python批量解压 二.python批量压缩 一.python批量解压 提示:如果是重要数据解压前请先备份,解压后会覆盖原压缩文件!! 解压前: 解压后:文件名为英文: 文件名中包含中文: 代码如下 import os import shutil import zipfile # 首先引入需要的工具包 # shutil为后期移动文件所需,可以忽略此项 # 路径改这里! #parent_path = r'输入路径,会解压该路径下的所有zip压缩文件' parent_path = r'E

  • Python中xml和dict格式转换的示例代码

    在做接口自动化的时候,请求数据之前都是JSON格式的,Python有自带的包来解决.最近在做APP的接口,遇到XML格式的请求数据,费了很大劲来解决,解决方式是:接口文档拿到的是XML,在线转化为json格式(目的是拿到xml数据的模板),存放到json文件中,根据接口名去提取. github原文介绍:使用XML的Python模块感觉就像您在使用JSON 链接:https://github.com/martinblech/xmltodict 下载xmltodict(pip install xml

  • python在linux环境下安装skimage的示例代码

    一.执行代码 yum install xz-devel yum install python-backports-lzma pip3 install scikit-image pip3 install backports.lzma 二.修改文件 修改文件路径 /usr/local/python3/lib/python3.6/lzma.py 修改文件部分内容 将 from _lzma import * from _lzma import _encode_filter_properties, _de

  • Python基于React-Dropzone实现上传组件的示例代码

    目录 实例演示 1. axios上传普通文件: 2. 大文件导入: 结语 这次我要讲述的是在React-Flask框架上开发上传组件的技巧.我目前主要以React开发前端,在这个过程中认识到了许多有趣的前端UI框架--React-Bootstrap.Ant Design.Material UI.Bulma等.而比较流行的上传组件也不少,而目前用户比较多的是jQuery-File-Upload和Dropzone,而成长速度快的新晋有Uppy和filepond.比较惋惜的是Fine-Uploader

  • Python与Appium实现手机APP自动化测试的示例代码

    目录 1.什么是Appium 2.启动一个app自动化程序的步骤 3.appium服务介绍 4. appium客户端使用 5.adb的使用 6.Appium启动过程分析 1.什么是Appium appium是一个开源的测试自动化框架,可以与原生的.混合的和移动的web应用程序一直使用.它使用WebDriver协议驱动IOS(内置的测试引擎xcuitest).Android(uiautomator2,Espresso)和Windows应用程序 原生应用程序:安卓程序是用JAVA或kotlin开发出

随机推荐