關于迷宮問題，常見會問能不能到達某點，以及打印到達的最短路徑。可以用回溯法+遞歸來解決

代碼一：dfs + 回溯

將矩陣外圍以及路障統一設置為-1

設置current_step和next_step兩個值。如果面臨的點大于next_step，或者從未走過，就可以對它遞歸

存儲矩陣：直接在原迷宮上修改，每個點標記的是從起點過來經過的步數，遇到0或者是比當前大至少2的，就考察

# -*- 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])

代碼二：也是回溯

這里0是可走，1是路障，用while來做循環。如果某點的附近有判斷可走的新點，就將新點append進stack，走過了標記為-1；如果四個方向都沒有，就從舊點從stack中pop掉，標上-1，進行回溯。

存儲矩陣：stack中存儲的0是可走，1是路障，-1是走過的或者是死路

maze = [

[1,1,1,1,1,1,1,1,1,1],

[1,0,0,1,0,0,0,1,0,1],

[1,0,0,1,0,0,0,1,0,1],

[1,0,0,0,0,1,1,0,0,1],

[1,0,1,1,1,0,0,0,0,1],

[1,0,0,0,1,0,0,0,0,1],

[1,0,1,0,0,0,1,0,0,1],

[1,0,1,1,1,0,1,1,0,1],

[1,1,0,0,0,0,0,1,0,1],

[1,1,1,1,1,1,1,1,1,1]

]

dirs = [lambda x, y: (x + 1, y),

lambda x, y: (x - 1, y),

lambda x, y: (x, y - 1),

lambda x, y: (x, y + 1)]

def mpath(x1, y1, x2, y2):

stack = []

stack.append((x1, y1))

while len(stack) > 0:

curNode = stack[-1]

if curNode[0] == x2 and curNode[1] == y2:

#到達終點

for p in stack:

print(p)

return True

for dir in dirs:

nextNode = dir(curNode[0], curNode[1])

if maze[nextNode[0]][nextNode[1]] == 0:

#找到了下一個

stack.append(nextNode)

maze[nextNode[0]][nextNode[1]] = -1 # 標記為已經走過，防止死循環

break

else:#四個方向都沒找到

maze[curNode[0]][curNode[1]] = -1 # 死路一條,下次別走了

stack.pop() #回溯

print("沒有路")

return False

mpath(1,1,8,8)

總結

以上是生活随笔為你收集整理的python迷宫问题的所有路径_python——迷宫问题总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。