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代码：

运行结果：

(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程序设计有所帮助。