本文實(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 把圖周圍加上一圈-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
  '''
  遍歷周圍4個(gè)點(diǎn):
    如果周圍節(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

PS：本站還有一個(gè)無(wú)限迷宮游戲，基于JS實(shí)現(xiàn)，提供給大家參考一下：

在線迷宮小游戲：
http://tools.jb51.net/games/migong

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》

希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。

最新評(píng)論