有一个迷宫,里面有些地方不可抵达(墙壁以及边界),有些地方可以抵达。从一个位置到下一个位置只能通过向上(或者向右、或者向下、或者向左)走一步来实现。从起点出发,如何找到一条到达终点的通路。
用二维矩阵来模拟迷宫地图,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)