# Python 實現走迷宮
###### tags: `python`
> 使用工具
> * vs code
> * python 3.7
- 提供本篇文章快速導覽
[ToC]
## 題目說明
給予一 `n x n` 矩陣 `maze` 與起點 `start` 終點 `end`，由起點走到終點並返回路徑與顯示已走訪之地圖。其中 `0` 為可走路徑， `1` 為牆壁，`2` 為已走訪，當走到終點時將該點值設為 `5`。
> 限制條件
> * 迷宮一定至少有一條可走路徑
## 條件準備
設矩陣 `maze`
```python=1
maze = [
[1, 1, 1, 1, 1],
[1, 0, 0, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 1, 0, 1],
[1, 1, 1, 1, 1],
]
```
設置起點 `start` 與終點 `end`
```python=
start = (1,1)
end = (3,3)
```
## 解題思路
在思考怎麼找出路徑之前，應該要先意識到要如何在陣列中移動，可以移動以後才將已走訪節點做處裡。同時間也會遇到走進死胡同的情況，所以也要另外處理走訪順序。
> 以下提供我的演算法
1. 設定起點位置與終點位置
2. 輸入起點、終點與迷宮
3. 設定一迴圈結束條件為找到終點
4. 尋找四周有沒有可走路徑
5. 如果有就將目前位置設為2
6. 前進到下一個位置
7. 將目前位置加進queue裡
8. 否則目前位置 = queue.pop()
9. 檢查是否走到終點
10. 如果是就將目前位置設為5
11. 結束迴圈
12. 否則回到步驟 1
13. 輸出已走訪後之地圖
## 實作
首先建立一函式 `findPath` 提供主程式呼叫，呼叫時需傳入 `maze`、`start`、`end` 三個參數，同時建立目前位置之 Hash Table `current` 與紀錄路徑之 deque `q` 並初始化。
```python=1
from collections import deque
def findPath(maze,startP,end):
# current 為目前位置，因還沒開始走訪，所以目前位置等於起點
cur = {'x':startP[1],'y':startP[0]}
# endP 為終點座標，預先建立方便待會來確認是否到終點
endP = {'x':end[1],'y':end[0]}
# q 為紀錄已走訪路徑的資料結構
q = deque({'x':cur['x'],'y':cur['y']})
```
接者設置一個 while 迴圈來走訪迷宮，結束目標是走到終點。迴圈結束時顯示地圖並回傳路徑。
```python=10
while True:
# 往下走
if maze[cur['y']+1][cur['x']] == 0:
maze[cur['y']][cur['x']] = 2
q.append({'x':cur['x'],'y':cur['y']+1})
cur['y'] = cur['y'] +1
# 往右走
elif maze[cur['y']][cur['x']+1] == 0:
maze[cur['y']][cur['x']] = 2
q.append({'x':cur['x']+1,'y':cur['y']})
cur['x'] = cur['x'] +1
# 往左走
elif maze[cur['y']][cur['x']-1] == 0:
maze[cur['y']][cur['x']] = 2
q.append({'x':cur['x']-1,'y':cur['y']})
cur['x'] = cur['x'] -1
# 往上走
elif maze[cur['y']-1][cur['x']] == 0:
maze[cur['y']][cur['x']] = 2
q.append({'x':cur['x'],'y':cur['y']-1})
cur['y'] = cur['y'] -1
# 都沒有可走路徑
else:
maze[cur['y']][cur['x']] = 2
cur = q.pop()
if len(q) == 0:
q.append({'x':cur['x'],'y':cur['y']})
# 檢查是否走到終點
if cur['x'] == endP['x'] and cur['y'] == endP['y']:
maze[cur['y']][cur['x']] = 5
break
# 顯示地圖並回傳路徑
showMaze(maze)
return q
```
最後在設立一個函式 `showMaze` 來輸出地圖狀態即可。
```python=50
def showMaze(maze):
for i in range(len(maze)):
for j in range(len(maze[0])):
print(maze[i][j],end=' ',sep=',')
print()
```
## 完整程式碼
```python=1
from collections import deque
def showMaze(maze):
for i in range(len(maze)):
for j in range(len(maze[0])):
print(maze[i][j],end=' ',sep=',')
print()
def findPath(maze,startP,end):
cur = {'x':startP[1],'y':startP[0]}
endP = {'x':end[1],'y':end[0]}
q = deque()
q.append({'x':cur['x'],'y':cur['y']})
while True:
if maze[cur['y']+1][cur['x']] == 0:
maze[cur['y']][cur['x']] = 2
q.append({'x':cur['x'],'y':cur['y']+1})
cur['y'] = cur['y'] +1
elif maze[cur['y']][cur['x']+1] == 0:
maze[cur['y']][cur['x']] = 2
q.append({'x':cur['x']+1,'y':cur['y']})
cur['x'] = cur['x'] +1
elif maze[cur['y']][cur['x']-1] == 0:
maze[cur['y']][cur['x']] = 2
q.append({'x':cur['x']-1,'y':cur['y']})
cur['x'] = cur['x'] -1
elif maze[cur['y']-1][cur['x']] == 0:
maze[cur['y']][cur['x']] = 2
q.append({'x':cur['x'],'y':cur['y']-1})
cur['y'] = cur['y'] -1
else:
maze[cur['y']][cur['x']] = 2
cur = q.pop()
if len(q) == 0:
q.append({'x':cur['x'],'y':cur['y']})
if cur['x'] == endP['x'] and cur['y'] == endP['y']:
maze[cur['y']][cur['x']] = 5
break
showMaze(maze)
print(f'最佳路徑為: {q}')
maze = [[1,1,1,1,1],
[1,0,0,0,1],
[1,0,1,0,1],
[1,0,1,0,1],
[1,1,1,1,1]]
start = (1,1)
end = (9,9)
findPath(maze,start,end)
```
## 總結
其實實現以上功能之程式碼的觀念就是 **BFS(廣度優先搜索)**，搭配一點點的 Hash Table 與 deque 即可完成迷宮之走訪，以上的概念與 **Backtracking(回溯法)** 非常相似，但不需要去紀錄完整的路徑，只需將已走訪的點關閉即可找出最短路徑，比起 Backtracking 我個人認為這個作法更接近 **Exhaustive attack** XD。
Sign in with Wallet
Connect another wallet