Python解決走迷宮問(wèn)題算法示例

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

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

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

問(wèn)題：

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

思路：

深度優(yōu)先遍歷，到達(dá)每一個(gè)點(diǎn)，記錄從起點(diǎn)到達(dá)每一個(gè)點(diǎn)的最短步數(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 把圖周?chē)由弦蝗?1 ，在深度優(yōu)先遍歷的時(shí)候防止出界
2 把所有障礙改成-1，把能走的地方改成0
3 每次遍歷經(jīng)歷某個(gè)點(diǎn)的時(shí)候，如果當(dāng)前節(jié)點(diǎn)值是0 把花費(fèi)的步數(shù)存到節(jié)點(diǎn)里
如果當(dāng)前節(jié)點(diǎn)值是-1 代表是障礙不遍歷它
如果走到當(dāng)前節(jié)點(diǎn)花費(fèi)的步數(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 是遍歷的時(shí)候防止出界的

默認(rèn)從左上角的點(diǎn)是入口右上角的點(diǎn)是出口

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
  '''
  遍歷周?chē)?個(gè)點(diǎn):
    如果周?chē)?jié)點(diǎn)不是-1 說(shuō)明 不是障礙 在此基礎(chǔ)上：
        里面是0 說(shuō)明沒(méi)遍歷過(guò) 我們把它修改成當(dāng)前所在位置步數(shù)加1
        里面比當(dāng)前的next_step大 說(shuō)明不是最優(yōu)方案 就修改它
        里面比當(dāng)前next_step說(shuō)明當(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])

運(yùn)行結(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