python迷宮問題深度優先遍歷實例
一、迷宮介紹
用python解迷宮問題,迷宮是一個二維列表,本次用深度優先解開迷宮問題。定義起點和終點,從一個位置到下一個位置隻能通過向上或下或左或右,走一步來實現,從起點出發,如何找到一條到達終點的通路。
二、深度優先遍歷
簡單那我們的案例來講就是,隨便選擇一條路,一直走,走不動瞭,再回頭重新選擇新的路
# 1 為墻,0 為路 maze = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 0, 1, 1, 1], [1, 0, 1, 1, 1, 1, 0, 0, 1, 1], [1, 0, 1, 0, 0, 0, 0, 0, 1, 1], [1, 0, 1, 0, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 0, 0, 0, 1, 1, 1], [1, 1, 1, 0, 0, 1, 0, 1, 1, 1], [1, 1, 1, 1, 1, 1, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], ]
首先我們先設置一個起點和終點
start = (1, 1) end = (8, 8)
判斷當前這個點,0就是路可以走,1為墻不能走
對於一個點的下一個點的坐標準說明:
- 上走:r – 1, c
- 下走:r + 1, c
- 左走:r, c – 1
- 右走:r, c + 1
那我們這個迷宮的某個一個點達到瞭不能走的地步瞭,就是死胡同瞭,它就得原路返回
這時我們就有一個概念,就是棧,棧的思想就是:先進後出
怎麼理解呢,可以舉一個小例子,就是食堂阿姨,每天早上蒸包子,他是一層一層放蒸籠
那放到最後,學生來吃包子,她是從上往往外拿,最上面就是最後放的,最下面是最先放的,所以就叫做先進後出
其實list就是一個棧,比如我們放一個空列表,然後我們用這個列表直接append
再用pop進行取出,就會取到append的最後一個元素
# 定義列表,列表裡面放的就是每一步走的坐標,[r, c] # 第一步就是起始位置,也就是start list01 = [start]
走過的路定義為2
row, col = now # python 裡的解構也叫解包 now包括兩個位置,一個行,一個列 maze[row][col] = 2 # 這個代表就是走過的點,為2,因為你走過的路是不能再走的,除瞭走不通返回的時候,也是為瞭走不通按原來走過的路原路返回
核心代碼:
if maze[row - 1][col] == 0: # 上方可以走 list01.append((row - 1, col)) continue elif maze[row][col + 1] == 0: # 右方可以走 list01.append((row, col + 1)) continue elif maze[row + 1][col] == 0: # 下方可以走 list01.append((row + 1, col)) continue elif maze[row][col - 1] == 0: # 左方可以走 list01.append((row, col - 1)) continue
最終代碼,可以運行一下試試:
maze = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 0, 1, 1, 1], [1, 0, 1, 1, 1, 1, 0, 0, 1, 1], [1, 0, 1, 0, 0, 0, 0, 0, 1, 1], [1, 0, 1, 0, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 0, 0, 0, 1, 1, 1], [1, 1, 1, 0, 0, 1, 0, 1, 1, 1], [1, 1, 1, 1, 1, 1, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], ] start = (1, 1) end = (8, 8) # 定義列表,列表裡面放的就是每一步走的坐標,[r, c] # 第一步就是起始位置,也就是start list01 = [start] # 定義循環,讓它走 # 列表裡最後存的就是下一步走的地方,當前列表有東西才能繼續走 while list01: # 當前走到的節點是哪一個節點,也就是最後走的一步,是哪一步,去列表的最後的一個值就是索引-1 now = list01[-1] if now == end: # 如果現在的now等於我們之前定義的終點end print(list01) print("出來瞭") break row, col = now # python 裡的解構也叫解包 now包括兩個位置,一個行,一個列 maze[row][col] = 2 # 這個代表就是走過的點,為2,因為你走過的路是不能再走的,除瞭走不通返回的時候,也就是為瞭走不通按原來走過的路原路返回 # continue 結束本次循環,從新開始判斷走路 if maze[row - 1][col] == 0: # 上方可以走 list01.append((row - 1, col)) continue elif maze[row][col + 1] == 0: # 右方可以走 list01.append((row, col + 1)) continue elif maze[row + 1][col] == 0: # 下方可以走 list01.append((row + 1, col)) continue elif maze[row][col - 1] == 0: # 左方可以走 list01.append((row, col - 1)) continue else: # 走不通過,直接循環幹掉每一步,重新調整路線 list01.pop() else: print("這個迷宮走不通")
總結
到此這篇關於python迷宮問題深度優先遍歷的文章就介紹到這瞭,更多相關python迷宮深度優先內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!