和室友打赌玩迷宫！输的买一个月的烟！还有Python过不了的迷宫吗

概述事情的起源昨天IG不是夺冠吗！心里真的很开心！恭喜IG夺冠！圆梦了，今天早上起床上课，无意在手机上看到一个迷宫的广告！然后室友也看到了，他是那种学习成绩比较优秀的，认为自己智商也非常高的，说这个太简单了！

事情的起源

昨天IG不是夺冠吗！心里真的很开心！恭喜IG夺冠！圆梦了，今天早上起床上课，无意在手机上看到一个迷宫的广告！然后室友也看到了，他是那种学习成绩比较优秀的，认为自己智商也非常高的，说这个太简单了！然后我就说你肯定过不了，就有了接下来的打赌，反正他玩了一上午都没有找到出口！我们的赌约是谁输了，谁就请对方一个月的烟钱！我平常的话丑的烟也不是很贵吗，就20来块一包左右的，然后我就欣然的接受了！然后我花了半个小时就写除了下面的这个算是个脚本吧！大家都知道什么是迷宫吧？给大家普及一下！

迷宫（Maze）指的是充满复杂通道，很难找到从其内部到达入口或从入口到达中心的道路，道路复杂难辨，人进去不容易出来的建筑物。

假设一个迷宫，它长这样（我自己画的，你也可以通过改变下面的矩阵从而改变迷宫的形状）。

起始点是红色小方块，终点是绿色的小方块，其中蓝色的■代表墙。

我们可以把迷宫抽象成一个矩阵，其中1代表墙，0代表有路，那么有

import numpy as npmaze=np.mat("""[ 1 1 1 1 1 1 1 1 1 1 1; 1 0 1 0 0 0 0 1 0 0 1; 1 0 1 0 1 1 0 1 0 1 1; 1 0 0 0 0 0 1 0 0 0 1; 1 1 1 1 1 0 1 1 0 1 1; 1 0 0 0 0 0 1 1 1 0 1; 1 1 1 0 1 1 1 0 0 0 1; 1 0 0 0 1 0 0 0 0 1 1; 1 0 1 0 0 0 1 1 0 0 1; 1 1 1 1 1 1 1 1 1 11]""",dtype=np.int8)

使用numpy模块的矩阵，不仅仅是它比双重List代表的矩阵好，还有的是把元素设置为int8，每个元素在-127到128变化即可（实际上根本用不到那么多），况且int8只占一个字节。

定义四个方向

dire=[(0,1),(1,0),(0,-1),(-1,0)]

进群：548377875   即可获取大量的学习资料以及大量的pdf哦！Python是一个非常神奇的东西！

我们理一下思路，走迷宫的决策是：

标记当前位置 从栈中d出一个位置和要走的方向，也就是当前位置和未知方向 看看未知方向，是否可以走。 如果有可以走，把当前位置和下一个未知方向压入栈。把新位置和一个未知方向压入栈，返回1步骤，如果未知方向不可以走，再探查下一个未知方向。如果发现是死路，退到之前的位置再看看。 下一个未知点是终点，搜索结束。返回路径 一直退到出发点直到栈长度为0，说明没有路径可以走到终点。

为什么要标记当前位置，我用一个小漫画说明

def mark(maze,pos): maze[pos[0],pos[1]]=2def passable(maze,pos): return maze[pos[0],pos[1]]==0

mark标记函数很简单，把pos在地图maze上标记为2，表示走过了。

passable函数表示是否可以走，如果位置pos值为0就可以走。

def st_find(maze,start,end): """maze为迷宫矩阵，start和end是开始点和结束点 返回一个List"""
if start==end:
特殊情况，起点就是终点
return [(start,0)]
st=[] #stack的缩写，表示栈
mark(maze,start)
st.append((start,0))
将开始位置和要探索的未知未知压入栈
while len(st)!=0:
只要还有没有探索完的地方就不会结束
pos,nxt=st.pop()
for i in range(nxt,4):
nextp=(pos[0]+dire[i][0],pos[1]+dire[i][1])
下一个探查点
if passable(maze,nextp):
st.append((pos,i+1))
如果可行，把下一个没探测的点压入栈
mark(maze,nextp)
st.append((nextp,0))
把新的位置等压入栈
if nextp == end:
发现新位置是终点，结束
return st
break
print("没有发现路径")
return []

就这样，一个基于栈做为搜索的函数就写成了，更重要的是，它是非递归的，如果用递归写虽然简洁可是不容易理解。

其中，基于栈为搜索方式的搜索方法叫深度优先搜索(Depth First Search)，基于队列的叫宽度优先搜索 (Breadth First Search)。

运行函数，返回[((1,2),((2,((3,3),4),5),((4,((5,((6,((7,((8,6),7),8),9),0)]

其中List的每一个元素的第一个代表坐标，将每一个元素链接起来就是路径。我们可以使用matplotlib画出迷宫和路线

import matplotlib.pyplot as pltimport matplotlib# 设置matplotlib正常显示中文和负号matplotlib.rcParams['Font.sans-serif']=['SimHei'] # 用黑体显示中文matplotlib.rcParams['axes.unicode_minus']=False # 正常显示负号st=st_find(maze,(8,9))x=[]y=[]for i in st: x.append(i[0][0]) y.append(i[0][1])plt.plot(x,y,'r')xq=[]yq=[]for i in range(10): for j in range(11): if maze[i,j]==1: xq.append(i) yq.append(j)plt.plot(xq,yq,'*')plt.Title('深度优先搜索找到迷宫的路径')plt.show()

有趣的是，走迷宫问题也可以使用递归来实现，具体 *** 作如下，代码很简洁，栈（运行栈）在运行的时候，在程序内部出现的，用于保存每层函数递归的信息。

def find_path(maze,pos,end): mark(maze,pos) #标记 if pos==end: #走到终点或者开始点就是终点 print(pos,end=' ') return True for i in range(4): nextp=(pos[0]+dire[i][0],pos[1]+dire[i][1]) #探索每一个可能性 if passable(maze,nextp): if find_path(maze,nextp,end):  #递归开始，如果这样一直递归下去递归到终点 print(pos,end=' ') #输出结果 return True return False

@H_502_90@

到此结束咯！嘿嘿，烟钱到手，开心啊！反正我一天也抽不了多少！大概一天就是一包左右，一个月也就三条左右就快了！我可不是刻意坑我室友的，你知道的大学当班长，一些外快还是随便就能混到的，比如帮忙申请一个助学金的名额，或者奖学金的名额，他就能得到一笔不菲的钱，所以反正也是他请我们吃饭抽烟啥的，我就收了也没关系啦，反正也是两个人一起抽的！并没有大家想的那样哦！

总结

以上是内存溢出为你收集整理的和室友打赌玩迷宫！输的买一个月的烟！还有Python过不了的迷宫吗全部内容，希望文章能够帮你解决和室友打赌玩迷宫！输的买一个月的烟！还有Python过不了的迷宫吗所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。