一、迷宮介紹
用python解迷宮問題，迷宮是一個二維列表，本次用深度優先解開迷宮問題。定義起點和終點，從一個位置到下一個位置只能通過向上或下或左或右，走一步來實現，從起點出發，如何找到一條到達終點的通路。
二、深度優先遍歷
簡單那我們的案例來講就是，隨便選擇一條路，一直走，走不動了，再回頭重新選擇新的路
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
# 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],] |
首先我們先設置一個起點和終點
|
1
2
|
start = (1, 1)end = (8, 8) |
判斷當前這個點，0就是路可以走，1為墻不能走
對于一個點的下一個點的坐標準說明：
- 上走：r - 1, c
- 下走：r + 1, c
- 左走：r, c - 1
- 右走：r, c + 1
那我們這個迷宮的某個一個點達到了不能走的地步了，就是死胡同了，它就得原路返回
這時我們就有一個概念，就是棧，棧的思想就是：先進后出
怎么理解呢，可以舉一個小例子，就是食堂阿姨，每天早上蒸包子，他是一層一層放蒸籠
那放到最后，學生來吃包子，她是從上往往外拿，最上面就是最后放的，最下面是最先放的，所以就叫做先進后出
其實list就是一個棧，比如我們放一個空列表，然后我們用這個列表直接append
再用pop進行取出，就會取到append的最后一個元素
|
1
2
3
|
# 定義列表，列表里面放的就是每一步走的坐標，[r, c]# 第一步就是起始位置，也就是startlist01 = [start] |
走過的路定義為2
|
1
2
3
4
|
row, col = now# python 里的解構也叫解包 now包括兩個位置，一個行，一個列maze[row][col] = 2# 這個代表就是走過的點，為2，因為你走過的路是不能再走的，除了走不通返回的時候，也是為了走不通按原來走過的路原路返回 |
核心代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
if maze[row - 1][col] == 0: # 上方可以走 list01.append((row - 1, col)) continueelif maze[row][col + 1] == 0: # 右方可以走 list01.append((row, col + 1)) continueelif maze[row + 1][col] == 0: # 下方可以走 list01.append((row + 1, col)) continueelif maze[row][col - 1] == 0: # 左方可以走 list01.append((row, col - 1)) continue |
最終代碼，可以運行一下試試：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
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]# 第一步就是起始位置，也就是startlist01 = [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迷宮深度優先內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://blog.csdn.net/Yxh666/article/details/117887077
