Python解決走迷宮問題算法示例

更新時間：2018年07月27日 14:15:11 作者：稀里糊涂林老冷

這篇文章主要介紹了Python解決走迷宮問題算法,結(jié)合實例形式分析了Python基于二維數(shù)組的深度優(yōu)先遍歷算法解決走迷宮問題相關(guān)操作技巧,需要的朋友可以參考下

本文實例講述了Python解決走迷宮問題算法。分享給大家供大家參考，具體如下：

問題：

輸入n * m 的二維數(shù)組表示一個迷宮
數(shù)字0表示障礙 1表示能通行
移動到相鄰單元格用1步

思路：

深度優(yōu)先遍歷，到達每一個點，記錄從起點到達每一個點的最短步數(shù)

初始化案例：

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 ，在深度優(yōu)先遍歷的時候防止出界
2 把所有障礙改成-1，把能走的地方改成0
3 每次遍歷經(jīng)歷某個點的時候，如果當(dāng)前節(jié)點值是0 把花費的步數(shù)存到節(jié)點里
如果當(dāng)前節(jié)點值是-1 代表是障礙不遍歷它
如果走到當(dāng)前節(jié)點花費的步數(shù)比里面存的小，就修改它

修改后的圖：

-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])
#深度優(yōu)先遍歷
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個點:
    如果周圍節(jié)點不是-1 說明 不是障礙 在此基礎(chǔ)上：
        里面是0 說明沒遍歷過 我們把它修改成當(dāng)前所在位置步數(shù)加1
        里面比當(dāng)前的next_step大 說明不是最優(yōu)方案 就修改它
        里面比當(dāng)前next_step說明當(dāng)前不是最優(yōu)方案，不修改
  '''
  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])

運行結(jié)果：

(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