Python 实现走迷宫深度优先回溯算法（优质代码）

#地图：0是可走的地方，1是障碍物     maze=np.array([[0,0,0,0,0],[0,1,0,1,0],[0,1,1,0,0],[0,1,1,0,0],[0,0,0,0,0]])

入口和出口：

    startP=Point(0,0)#起点坐标     endP=Point(4,4)#终点坐标

没有传送门

import numpyas np

''' 类:Point 用来标识坐标点 '''classPoint(object):def__init__(self,x,y):         self.row=x         self.col=y

''' 函数：判断两个点是否相同 参数:     Point p1      Point p2 '''defisSamePoint(p1,p2):if(p1.row==p2.row)and(p1.col==p2.col):returnTrueelse:returnFalse''' 函数：获取相邻未被访问的节点(上下左右) 参数说明：     mark：节点标记     point：节点      m：行      n：列 '''defgetAdjacentNotVisitedNode(mark,point,m,n):     resP=Point(-1,-1)if(point.row-1>=0)and(mark[point.row-1][point.col]==0):         resP.row=point.row-1         rep.col=point.colreturn resPif(point.col+1<n)and(mark[point.row][point.col+1]==0):         resP.row=point.row         resP.col=point.col+1return resPif(point.row+1<m)and(mark[point.row+1][point.col]==0):         resP.row=point.row+1         resP.col=point.colreturn resPif(point.col-1>=0)and(mark[point.row][point.col-1]==0):         resP.row=point.row         resP.col=point.col-1return resPreturn resP

''' 函数：寻路函数 参数：     maze：地图     m：行      n：列     pointStack：点栈，用于存放路径 '''defmazePath(maze,m,n,startP,endP,pointStack):if(maze[startP.row][startP.col]==1)or(maze[endP.row][endP.col]==1):return#     mark=maze#将起点入栈     pointStack.append(startP)     mark[startP.row][startP.col]=0#栈不空并且栈顶元素不为结束节点     ptop=pointStack[-1]while(len(pointStack)!=0)and(isSamePoint(ptop,endP)==False):         ptop=pointStack[-1]         adjacentNotVisitedNode=getAdjacentNotVisitedNode(mark,ptop,m,n)if adjacentNotVisitedNode.row==-1:             pointStack.pop()continue         mark[adjacentNotVisitedNode.row][adjacentNotVisitedNode.col]=1         pointStack.append(adjacentNotVisitedNode)

defmain():#地图：0是可走的地方，1是障碍物     maze=np.array([[0,0,0,0,0],[0,1,0,1,0],[0,1,1,0,0],[0,1,1,0,0],[0,0,0,0,0]])      startP=Point(0,0)#起点坐标     endP=Point(4,4)#终点坐标          pointStack=[]#设置点栈     mazePath(maze,5,5,startP,endP,pointStack)#执行寻路函数iflen(pointStack)==0:print('Died.....No way can go')else:         tmpStack=[]print('Path:')whilelen(pointStack)>0:             tmpStack.append(pointStack[-1])             pointStack.pop()whilelen(tmpStack)>0:             p=tmpStack.pop()print('<{},{}>'.format(p.row,p.col))if __name__=="__main__":     main()

import numpyas np''' 类:Point 用来标识坐标点 '''classPoint(object):def__init__(self,x,y):         self.row=x         self.col=y''' 函数：判断两个点是否相同 参数:     Point p1      Point p2 '''defisSamePoint(p1,p2):if(p1.row==p2.row)and(p1.col==p2.col):returnTrueelse:returnFalse''' 函数：获取相邻未被访问的节点(上下左右) 参数说明：     mark：节点标记     point：节点      m：行      n：列 '''defgetAdjacentNotVisitedNode(mark,point,m,n):     resP=Point(-1,-1)if(point.row-1>=0)and(mark[point.row-1][point.col]==0):         resP.row=point.row-1         rep.col=point.colreturn resPif(point.col+1<n)and(mark[point.row][point.col+1]==0):         resP.row=point.row         resP.col=point.col+1return resPif(point.row+1<m)and(mark[point.row+1][point.col]==0):         resP.row=point.row+1         resP.col=point.colreturn resPif(point.col-1>=0)and(mark[point.row][point.col-1]==0):         resP.row=point.row         resP.col=point.col-1return resPreturn resP''' 函数：寻路函数 参数：     maze：地图     m：行      n：列     pointStack：点栈，用于存放路径 '''defmazePath(maze,m,n,startP,endP,pointStack):if(maze[startP.row][startP.col]==1)or(maze[endP.row][endP.col]==1):return#     mark=maze#将起点入栈     pointStack.append(startP)     mark[startP.row][startP.col]=0#栈不空并且栈顶元素不为结束节点     ptop=pointStack[-1]while(len(pointStack)!=0)and(isSamePoint(ptop,endP)==False):         ptop=pointStack[-1]         adjacentNotVisitedNode=getAdjacentNotVisitedNode(mark,ptop,m,n)if adjacentNotVisitedNode.row==-1:             pointStack.pop()continue         mark[adjacentNotVisitedNode.row][adjacentNotVisitedNode.col]=1         pointStack.append(adjacentNotVisitedNode)defmain():#地图：0是可走的地方，1是障碍物     maze=np.array([[0,0,0,0,0],[0,1,0,1,0],[0,1,1,0,0],[0,1,1,0,0],[0,0,0,0,0]])      startP=Point(0,0)#起点坐标     endP=Point(4,4)#终点坐标          pointStack=[]#设置点栈     mazePath(maze,5,5,startP,endP,pointStack)#执行寻路函数iflen(pointStack)==0:print('Died.....No way can go')else:         tmpStack=[]print('Path:')whilelen(pointStack)>0:             tmpStack.append(pointStack[-1])             pointStack.pop()whilelen(tmpStack)>0:             p=tmpStack.pop()print('<{},{}>'.format(p.row,p.col))if __name__=="__main__":     main()

输出寻路路径的点坐标：