迷宮問題
問題描述：
迷宮可用方陣 [m, n] 表示，0 表示可通過，1 表示不能通過。若要求左上角 (0, 0) 進入，設(shè)計算法尋求一條能從右下角 (m-1, n-1) 出去的路徑。
示例圖：
此示例圖基本參數(shù)為：
- m：對應(yīng)
- x 軸n：對應(yīng) y 軸
- 綠色線代表期望輸出的路徑
算法思路
- 標記當前所在位置
- 如果此時所在位置為終點，說明可以到達終點，退出遞歸；
否則，則存在 4 種可能的移動方向即上、下、左、右，遍歷這 4 個方向，如果這 4 個方向存在相鄰值為 0 的點，則將當前點坐標標記為該相鄰值為 0 的點坐標，進入遞歸
直觀理解為：
上圖中紅色圈的相鄰值為 0 的點有 3 個，則會依次遍歷這 3 個點尋求某一條件并進入遞歸
實現(xiàn)過程
標記函數(shù)
|
1
2
3
4
5
6
7
|
def mark(maze, pos): """ 標記函數(shù)，用來標記歷史走過的位置 :param maze: 一個 m*n 大小的二維矩陣迷宮 :param pos: 當前需要標記的位置坐標 pos = (x, y)，x = pos[0], y = pos[1] """ maze[pos[0]][pos[1]] = 2 # 將走過的位置標記為 2 |
移動函數(shù)
|
1
2
3
4
5
6
7
8
|
def move(maze, pos): """ 移動函數(shù)，用來測試當前位置是否可繼續(xù)移動，移動條件為當前位置為 0 :param maze: 一個 m*n 大小的二維矩陣迷宮 :param pos: 當前需要標記的位置坐標 pos = (x, y)，x = pos[0], y = pos[1] :return: bool 類型 """ return maze[pos[0]][pos[1]] == 0 |
核心函數(shù) - 路徑查找函數(shù)
|
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
|
def find_path(maze, start, end): """ 路徑查找函數(shù) :param maze: 一個 m*n 大小的二維矩陣迷宮 :param start: 起始點位置坐標，start = (1, 1) :param end: 終點坐標，end = (m, n) :return: bool 類型 """ mark(maze, start) # 將起始位置標記 if start == end: # 路徑查找（遞歸）終止條件為到達終點 move_path.append(start) return True # 未到達終點時，存在 4 種可能的移動方向，即上 (-1, 0)，下 (1, 0)，左 (0, -1)，右 (0, 1) move_direction = [ (-1, 0), (1, 0), (0, -1), (0, 1) ] direction = ['↑', '↓', '←', '→'] for i in range(4): # 遍歷 4 種可能的方向 next_start = (start[0] + move_direction[i][0], start[1] + move_direction[i][1]) # 下一個可能的起始點坐標 if move(maze, next_start): # 找出存在 0 即可移動的下一個起始點坐標，進入遞歸 if find_path(maze, next_start, end): # 這里之所以仍然添加起始點坐標是因為當查詢到下一個位置就是終點或者可到達終點時記錄此時位置 move_path.append(start) path_direction.append(direction[i]) # 記錄路徑方向 return True return False # 遍歷遞歸了 4 種可能方向后仍不能到達終點則說明無法走出迷宮 |
算法到這里基本上已經(jīng)算完成，整體上不算太復雜
美化輸出
生成帶有移動路徑數(shù)據(jù)的迷宮矩陣
|
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
|
def path_maze(maze, directions_map): """ 生成帶有移動路徑的迷宮矩陣 :param maze: 一個 m*n 大小的二維矩陣迷宮 :param directions_map: 一個記錄移動方向坐標的字典，有 ↑，↓，←，→ 4 個元素 :return: path_maze """ n, m = len(maze[0]), len(maze) for x in range(1, m-1): for y in range(1, n-1): maze[x][y] = maze[x][y] if maze[x][y] != 2 else 0 # 將標記的 2 還原為 0 for x in range(m): for i in range(1, 2 * n - 1, 2): maze[x].insert(i, ' ') # 重初始化 maze，在每兩個元素間插入占位符 ' ' 3 個空格 for x in range(1, 2 * m - 1, 2): maze.insert(x, [' ', ' '] * (n-1) + ['']) # 插入兩種空格占位符 ' ' 和 ' ' for direction in directions_map: for directions_position in directions_map[direction]: i, j = directions_position i = 2 * i j = 2 * j if direction == "↑": maze[i - 1][j] = "↑" if direction == "↓": maze[i + 1][j] = "↓" if direction == "←": maze[i][j] = " ← " if direction == "→": maze[i][j + 1] = " → " return maze |
生成的帶路徑數(shù)據(jù)的迷宮矩陣部分數(shù)據(jù)截圖如下：
美化打印迷宮矩陣
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
def print_maze(maze, text='原始迷宮為：', end1=' ', end2='\n\n', xs=0, xe=0, ys=0, ye=0): """ 輸出迷宮矩陣，非必要，可注釋刪除 :param maze: 一個 m*n 大小的二維矩陣迷宮 :param text: 輸出提示 :param end1: 控制每行尾結(jié)束符 :param end2: 控制每行尾結(jié)束符 :param xs: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出 :param xe: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出 :param ys: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出 :param ye: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出 """ print(text) n, m = len(maze[0]), len(maze) for x in range(xs, m-xe): for y in range(ys, n-ye): print(maze[x][y], end=end1) print(end=end2) |
最終輸出結(jié)果：
效果尚可
完整代碼
|
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
# -*- coding: utf-8 -*-"""Created on 2020/1/11 10:51Author : zxtFile : maze_recursion.pySoftware: PyCharm"""from random import randintdef mark(maze, pos): """ 標記函數(shù)，用來標記歷史走過的位置 :param maze: 一個 m*n 大小的二維矩陣迷宮 :param pos: 當前需要標記的位置坐標 pos = (x, y)，x = pos[0], y = pos[1] """ maze[pos[0]][pos[1]] = 2 # 將走過的位置標記為 2def move(maze, pos): """ 移動函數(shù)，用來測試當前位置是否可繼續(xù)移動，移動條件為當前位置為 0 :param maze: 一個 m*n 大小的二維矩陣迷宮 :param pos: 當前需要標記的位置坐標 pos = (x, y)，x = pos[0], y = pos[1] :return: bool 類型 """ return maze[pos[0]][pos[1]] == 0move_path = [] # 記錄能成功到達出口的移動路徑坐標path_direction = [] # 記錄能成功到達出口的移動路徑方向def find_path(maze, start, end): """ 路徑查找函數(shù) :param maze: 一個 m*n 大小的二維矩陣迷宮 :param start: 起始點位置坐標，start = (1, 1) :param end: 終點坐標，end = (m, n) :return: bool 類型 """ mark(maze, start) # 將起始位置標記 if start == end: # 路徑查找（遞歸）終止條件為到達終點 move_path.append(start) return True # 未到達終點時，存在 4 種可能的移動方向，即上 (-1, 0)，下 (1, 0)，左 (0, -1)，右 (0, 1) move_direction = [ (-1, 0), (1, 0), (0, -1), (0, 1) ] direction = ['↑', '↓', '←', '→'] for i in range(4): # 遍歷 4 種可能的方向 next_start = (start[0] + move_direction[i][0], start[1] + move_direction[i][1]) # 下一個可能的起始點坐標 if move(maze, next_start): # 找出存在 0 即可移動的下一個起始點坐標，進入遞歸 if find_path(maze, next_start, end): # 這里之所以仍然添加起始點坐標是因為當查詢到下一個位置就是終點或者可到達終點時記錄此時位置 move_path.append(start) path_direction.append(direction[i]) # 記錄路徑方向 return True return False # 遍歷遞歸了 4 種可能方向后仍不能到達終點則說明無法走出迷宮def gen_maze(m, n): """ 生成隨機迷宮陣列 :param m: int 類型 :param n: int 類型 :return: maze """ m += 2 n += 2 # m 和 n 均 +2 是為了構(gòu)造最外層的 1 maze = [[1 for i in range(n)] for j in range(m)] # 初始化大小為 m * n，值全為 1 的二維矩陣 for x in range(1, m-1): for y in range(1, n-1): """ 這里 x, y 取值范圍為 x ∈ [1, m-1)，y ∈ [1, n-1) 是因為我們令此迷宮的最外層（四周）均為 1，如： 考察 3 * 3 矩陣，一種可能的陣列為： [ _ |←--- n:y ---→| ↑ [1, 1, 1, 1, 1], | [1, 0, 1, 0, 1], m:x [1, 0, 0, 1, 1], | [1, 1, 0, 0, 1], ↓ [1, 1, 1, 1, 1] ] """ if (x == 1 and y == 1) or (x == m - 2 and y == n - 2): maze[x][y] = 0 # 起始點和終點必為 0 else: maze[x][y] = randint(0, 1) # 在最外層均為 1 的情況下內(nèi)部隨機取 0，1 return mazedef print_maze(maze, text='原始迷宮為：', end1=' ', end2='\n\n', xs=0, xe=0, ys=0, ye=0): """ 輸出迷宮矩陣，非必要，可注釋刪除 :param maze: 一個 m*n 大小的二維矩陣迷宮 :param text: 輸出提示 :param end1: 控制每行尾結(jié)束符 :param end2: 控制每行尾結(jié)束符 :param xs: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出 :param xe: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出 :param ys: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出 :param ye: 控制是否輸出最上方的 1 環(huán)，0 為輸出，1 為不輸出 """ print(text) n, m = len(maze[0]), len(maze) for x in range(xs, m-xe): for y in range(ys, n-ye): print(maze[x][y], end=end1) print(end=end2)def path_maze(maze, directions_map): """ 生成帶有移動路徑的迷宮矩陣 :param maze: 一個 m*n 大小的二維矩陣迷宮 :param directions_map: 一個記錄移動方向坐標的字典，有 ↑，↓，←，→ 4 個元素 :return: path_maze """ n, m = len(maze[0]), len(maze) for x in range(1, m-1): for y in range(1, n-1): maze[x][y] = maze[x][y] if maze[x][y] != 2 else 0 # 將標記的 2 還原為 0 for x in range(m): for i in range(1, 2 * n - 1, 2): maze[x].insert(i, ' ') # 重初始化 maze，在每兩個元素間插入占位符 ' ' 3 個空格 for x in range(1, 2 * m - 1, 2): maze.insert(x, [' ', ' '] * (n-1) + ['']) # 插入兩種空格占位符 ' ' 和 ' ' for direction in directions_map: for directions_position in directions_map[direction]: i, j = directions_position i = 2 * i j = 2 * j if direction == "↑": maze[i - 1][j] = "↑" if direction == "↓": maze[i + 1][j] = "↓" if direction == "←": maze[i][j] = " ← " if direction == "→": maze[i][j + 1] = " → " return mazedef main(): # maze = gen_maze(m=10, n=12) maze = \ [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1], [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1], [1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1], [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1], [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1], [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1], [1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1], [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1], [1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1], [1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ] # 輸入樣式矩陣，這里最外層用 1 環(huán)包圍住，目的是方便后續(xù)的處理，可以用 gen_maze() 函數(shù)自生成 print_maze(maze) if find_path(maze, start=(1, 1), end=(10, 12)): mp = move_path[::-1] pd = path_direction[::-1] # 這里 pos[0] 和 pos[1] 都要 -1 是因為原來的遞歸計算中存在最外層的 1 環(huán) print('坐標移動順序為:', [(pos[0]-1, pos[1]-1) for pos in mp]) path_direction_map = { '↑': [], '↓': [], '←': [], '→': [] } # 路徑方向的映射表 for i in range(len(pd)): path_direction_map[pd[i]].append(mp[i]) maze = path_maze(maze, path_direction_map) print_maze(maze, text='迷宮移動路徑為：', end1='', end2='\n', xs=1, xe=1, ys=1, ye=1) else: print('此迷宮無解')if __name__ == '__main__': main() |
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/qq_40772371/article/details/103938992
