一、迷宮介紹
用python解迷宮問(wèn)題，迷宮是一個(gè)二維列表，本次用深度優(yōu)先解開迷宮問(wèn)題。定義起點(diǎn)和終點(diǎn)，從一個(gè)位置到下一個(gè)位置只能通過(guò)向上或下或左或右，走一步來(lái)實(shí)現(xiàn)，從起點(diǎn)出發(fā)，如何找到一條到達(dá)終點(diǎn)的通路。
二、深度優(yōu)先遍歷
簡(jiǎn)單那我們的案例來(lái)講就是，隨便選擇一條路，一直走，走不動(dòng)了，再回頭重新選擇新的路
# 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],
]
首先我們先設(shè)置一個(gè)起點(diǎn)和終點(diǎn)
start = (1, 1)
end = (8, 8)
判斷當(dāng)前這個(gè)點(diǎn)，0就是路可以走，1為墻不能走
對(duì)于一個(gè)點(diǎn)的下一個(gè)點(diǎn)的坐標(biāo)準(zhǔn)說(shuō)明：
- 上走：r - 1, c
- 下走：r + 1, c
- 左走：r, c - 1
- 右走：r, c + 1
那我們這個(gè)迷宮的某個(gè)一個(gè)點(diǎn)達(dá)到了不能走的地步了，就是死胡同了，它就得原路返回
這時(shí)我們就有一個(gè)概念，就是棧，棧的思想就是：先進(jìn)后出
怎么理解呢，可以舉一個(gè)小例子，就是食堂阿姨，每天早上蒸包子，他是一層一層放蒸籠
那放到最后，學(xué)生來(lái)吃包子，她是從上往往外拿，最上面就是最后放的，最下面是最先放的，所以就叫做先進(jìn)后出
其實(shí)list就是一個(gè)棧，比如我們放一個(gè)空列表，然后我們用這個(gè)列表直接append
再用pop進(jìn)行取出，就會(huì)取到append的最后一個(gè)元素
# 定義列表，列表里面放的就是每一步走的坐標(biāo)，[r, c]
# 第一步就是起始位置，也就是start
list01 = [start]
走過(guò)的路定義為2
row, col = now
# python 里的解構(gòu)也叫解包 now包括兩個(gè)位置，一個(gè)行，一個(gè)列
maze[row][col] = 2
# 這個(gè)代表就是走過(guò)的點(diǎn)，為2，因?yàn)槟阕哌^(guò)的路是不能再走的，除了走不通返回的時(shí)候，也是為了走不通按原來(lái)走過(guò)的路原路返回
核心代碼：
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
最終代碼，可以運(yùn)行一下試試：
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)
# 定義列表，列表里面放的就是每一步走的坐標(biāo)，[r, c]
# 第一步就是起始位置，也就是start
list01 = [start]
# 定義循環(huán)，讓它走
# 列表里最后存的就是下一步走的地方，當(dāng)前列表有東西才能繼續(xù)走
while list01:
# 當(dāng)前走到的節(jié)點(diǎn)是哪一個(gè)節(jié)點(diǎn)，也就是最后走的一步，是哪一步，去列表的最后的一個(gè)值就是索引-1
now = list01[-1]
if now == end: # 如果現(xiàn)在的now等于我們之前定義的終點(diǎn)end
print(list01)
print("出來(lái)了")
break
row, col = now
# python 里的解構(gòu)也叫解包 now包括兩個(gè)位置，一個(gè)行，一個(gè)列
maze[row][col] = 2
# 這個(gè)代表就是走過(guò)的點(diǎn)，為2，因?yàn)槟阕哌^(guò)的路是不能再走的，除了走不通返回的時(shí)候，也就是為了走不通按原來(lái)走過(guò)的路原路返回
# continue 結(jié)束本次循環(huán)，從新開始判斷走路
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: # 走不通過(guò)，直接循環(huán)干掉每一步，重新調(diào)整路線
list01.pop()
else:
print("這個(gè)迷宮走不通")
總結(jié)
到此這篇關(guān)于python迷宮問(wèn)題深度優(yōu)先遍歷的文章就介紹到這了,更多相關(guān)python迷宮深度優(yōu)先內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:- Python深度優(yōu)先算法生成迷宮
- 10分鐘教你用python動(dòng)畫演示深度優(yōu)先算法搜尋逃出迷宮的路徑
