---
# System prepended metadata

title: Python 實現走迷宮
tags: [python]

---

# 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。