使用Python解决迷宫问题

2022-08-31 10:56:34

  有一个迷宫,里面有些地方不可抵达(墙壁以及边界),有些地方可以抵达。从一个位置到下一个位置只能通过向上(或者向右、或者向下、或者向左)走一步来实现。从起点出发,如何找到一条到达终点的通路。

  用二维矩阵来模拟迷宫地图,1代表该位置不可达,0代表该位置可达。每走过一个位置就将地图的对应位置标记,以免重复。找到通路后打印每一步的坐标,最终到达终点位置。

maze=[[1,1,1,1,1,1,1,1,1],[1,0,1,1,1,0,0,1,1],[1,0,1,1,0,0,0,0,1],[1,0,1,1,0,1,1,0,1],[1,0,0,0,0,1,1,0,1],[1,1,1,0,1,1,1,1,1],[1,1,1,0,1,0,0,0,1],[1,1,1,0,0,0,1,0,1],[1,1,1,1,1,1,1,1,1],]

方向的选择

# 向上 r-1,c
# 向右 r,c+1
# 向下 r+1,c
# 向左 r,c-1

起点与终点的设置

start=(1,1)
end=(7,7)

开始核心代码

这里选用栈来解决问题

#先创建一个列表,同时放入起点的坐标
lst=[start]#建立一个while循环,条件当lst不为空时一直循环while lst:#查询当前所处位置
	now=lst[-1]#当当前所处位置与终点坐标相等时,就代表已经到达了出口if now==end:print("抵达终点")print(lst)break#解包或者解构
	row,columns=now#将走过的位置坐标记号改变,用以区分,以免重复
	maze[row][columns]=2#判断当前位置上方的标记,如果为0就将坐标放入栈if maze[row-1][columns]==0:# 向上
		lst.append((row-1,columns))continue#判断当前位置右方的标记,如果为0就将坐标放入栈elif maze[row][columns+1]==0:# 向右
		lst.append((row,columns+1))continue#判断当前位置下方的标记,如果为0就将坐标放入栈elif maze[row+1][columns]==0:# 向下
		lst.append((row+1,columns))continue#判断当前位置左方的标记,如果为0就将坐标放入栈elif maze[row][columns-1]==0:# 向左
		lst.append((row,columns-1))continue#当四周都判断后,发现没有可走的路径,则pop,重新从上一个坐标开始寻找没有被标记的路径else:# 四周没有可继续的路径
		lst.pop()else:#一直pop,直到栈里没有元素了,就说明找不到终点print("没有找到终点")

拓展

结果二维矩阵显示

这里采用深拷贝

引入copy模块

import copy# 深拷贝,完全独立的两个对象
mazeNew=copy.deepcopy(maze)#根据最后栈里面的元素坐标来改变标记for iin lst:
	r,c=i
	mazeNew[r][c]=8for jin mazeNew:print(j)
  • 作者:Pumpk1n?
  • 原文链接:https://blog.csdn.net/qq_43612801/article/details/120721214
    更新时间:2022-08-31 10:56:34