本文實例講述了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 -*-def init():  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__":  graph = []  init()  deepFirstSearch(-1,1,1)  print(graph[1][5])