python迷宫问题代码_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
python新手代码示例
-1 0 0 0 0 0 -1
-1 -1 -1 -1 -1 -1 -1
外周的-1 是遍历的时候防⽌出界的
默认从左上⾓的点是⼊⼝ 右上⾓的点是出⼝
Python代码：
global graph
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])
#深度优先遍历
def deepFirstSearch( steps , x, y ):
global graph
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说明当前不是最优⽅案，不修改
'''
if not(x-1== 1 and y==1) and graph[x-1][y] != -1 and ( graph[x-1][y]>next_step or graph[x-1][y] ==0 ) : #左deepFirstSearch(current_step, x-1 , y )
if not(x == 1 and y-1==1) and graph[x][y-1] != -1 and ( graph[x][y-1]>next_step or graph[x][y-1] ==0 ) : #上deepFirstSearch(current_step, x , y-1 )
if not(x == 1 and y+1==1) and graph[x][y+1] != -1 and ( graph[x][y+1]>next_step or graph[x][y+1]==0 ) : #下deepFirstSearch(current_step, x , y+1 )
if not(x+1== 1 and y==1) and graph[x+1][y] != -1 and ( graph[x+1][y]>next_step or graph[x+1][y]==0 ) : #右deepFirstSearch(current_step, x+1 , y )
if __name__ == "__main__":
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, 1, 5)
12
PS：本站还有⼀个⽆限迷宫游戏，基于JS实现，提供给⼤家参考⼀下：
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python编码操作技巧总结》、《Python函数使⽤技巧总结》、《Python字符串操作技巧汇总》及《Python⼊门与进阶经典教程》
希望本⽂所述对⼤家Python程序设计有所帮助。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。