Python解决走迷宫问题算法示例
本文实例讲述了Python解决走迷宫问题算法。分享给大家供大家参考，具体如下：
问题：
输入n*m的二维数组表示一个迷宫
数字0表示障碍1表示能通行
移动到相邻单元格用1步
思路：
深度优先遍历，到达每一个点，记录从起点到达每一个点的最短步数
初始化案例：
1 1 0 1 1
1 0 1 1 1
1 0 1 0 0
1 0 1 1 1
1 1 1 0 1
1 1 1 1 1
1把图周围加上一圈-1，在深度优先遍历的时候防止出界
2把所有障碍改成-1，把能走的地方改成0
3每次遍历经历某个点的时候，如果当前节点值是0把花费的步数存到节点里
如果当前节点值是-1代表是障碍不遍历它
如果走到当前节点花费的步数比里面存的小，就修改它
修改后的图：
-1 -1 -1 -1 -1 -1 -1
-1 0 0 -1 0 0 -1
-1 0 -1 0 0 0 -1
-1 0 -1 0 -1 -1 -1
-1 0 -1 0 0 0 -1
-1 0 0 0 -1 0 -1
-1 0 0 0 0 0 -1
-1 -1 -1 -1 -1 -1 -1
外周的-1是遍历的时候防止出界的
默认从左上角的点是入口右上角的点是出口
Python代码：
#-*-coding:utf-8-*- definit(): globalgraph graph.append([-1,-1,-1,-1,-1,-1,-1]) graph.append([-1,0,0,-1,0,0,-1]) graph.append([-1,0,-1,0,0,0,-1]) graph.append([-1,0,-1,0,-1,-1,-1]) graph.append([-1,0,-1,0,0,0,-1]) graph.append([-1,0,0,0,-1,0,-1]) graph.append([-1,0,0,0,0,0,-1]) graph.append([-1,-1,-1,-1,-1,-1,-1]) #深度优先遍历 defdeepFirstSearch(steps,x,y): globalgraph current_step=steps+1 print(x,y,current_step) graph[x][y]=current_step next_step=current_step+1 ''' 遍历周围4个点: 如果周围节点不是-1说明不是障碍在此基础上： 里面是0说明没遍历过我们把它修改成当前所在位置步数加1 里面比当前的next_step大说明不是最优方案就修改它 里面比当前next_step说明当前不是最优方案，不修改 ''' ifnot(x-1==1andy==1)andgraph[x-1][y]!=-1and(graph[x-1][y]>next_steporgraph[x-1][y]==0):#左 deepFirstSearch(current_step,x-1,y) ifnot(x==1andy-1==1)andgraph[x][y-1]!=-1and(graph[x][y-1]>next_steporgraph[x][y-1]==0):#上 deepFirstSearch(current_step,x,y-1) ifnot(x==1andy+1==1)andgraph[x][y+1]!=-1and(graph[x][y+1]>next_steporgraph[x][y+1]==0):#下 deepFirstSearch(current_step,x,y+1) ifnot(x+1==1andy==1)andgraph[x+1][y]!=-1and(graph[x+1][y]>next_steporgraph[x+1][y]==0):#右 deepFirstSearch(current_step,x+1,y) if__name__=="__main__": graph=[] init() deepFirstSearch(-1,1,1) print(graph[1][5])
运行结果：
(1,1,0)
(1,2,1)
(2,1,1)
(3,1,2)
(4,1,3)
(5,1,4)
(5,2,5)
(5,3,6)
(4,3,7)
(3,3,8)
(2,3,9)
(2,4,10)
(1,4,11)
(1,5,12)
(2,5,13)
(2,5,11)
(4,4,8)
(4,5,9)
(5,5,10)
(6,5,11)
(6,4,12)
(6,3,13)
(6,2,14)
(6,1,15)
(6,3,7)
(6,2,8)
(6,1,9)
(6,4,8)
(6,5,9)
(6,2,6)
(6,1,7)
(6,1,5)
12
PS：本站还有一个无限迷宫游戏，基于JS实现，提供给大家参考一下：
在线迷宫小游戏：
http://tools.jb51.net/games/migong
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。