題目

給你一個 m x n 的迷宮矩陣 maze （下標從 0 開始），矩陣中有空格子（用 ‘.’ 表示）和墻（用 ‘+’ 表示）。同時給你迷宮的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一開始所在格子的行和列。
每一步操作，你可以往 上，下，左 或者 右 移動一個格子。你不能進入墻所在的格子，你也不能離開迷宮。你的目標是找到離 entrance 最近 的出口。出口 的含義是 maze 邊界 上的 空格子。entrance 格子 不算 出口。
請你返回從 entrance 到最近出口的最短路徑的 步數 ，如果不存在這樣的路徑，請你返回 -1 。

一、代碼實現

func nearestExit(maze [][]byte, entrance []int) int {m := len(maze)if m == 0 {return -1}n := len(maze[0])if n == 0 {return -1}entranceRow, entranceCol := entrance[0], entrance[1]queue := [][]int{{entranceRow, entranceCol}}maze[entranceRow][entranceCol] = '+' // 標記為已訪問directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}steps := 0for len(queue) > 0 {levelSize := len(queue)for i := 0; i < levelSize; i++ {cell := queue[0]queue = queue[1:]row, col := cell[0], cell[1]for _, dir := range directions {newRow := row + dir[0]newCol := col + dir[1]// 檢查邊界if newRow < 0 || newRow >= m || newCol < 0 || newCol >= n {continue}// 檢查是否可走且未訪問if maze[newRow][newCol] == '+' {continue}// 檢查是否是出口if isExit(newRow, newCol, entranceRow, entranceCol, m, n) {return steps + 1}// 標記為已訪問并入隊maze[newRow][newCol] = '+'queue = append(queue, []int{newRow, newCol})}}steps++}return -1
}func isExit(r, c, entranceR, entranceC, m, n int) bool {// 位于邊界且不是入口return (r == 0 || r == m-1 || c == 0 || c == n-1) && !(r == entranceR && c == entranceC)
}

二、算法分析

1. 核心思路

• 廣度優先搜索（BFS）：從入口出發分層擴展，首次到達邊界即最短路徑
• 出口判定：當節點位于迷宮邊界且非入口時視為合法出口
• 狀態管理：使用二維數組記錄訪問狀態，避免重復遍歷

2. 關鍵步驟

1. 隊列初始化：將入口位置加入隊列，步數設為0
2. 分層遍歷：每次處理一層節點，檢查是否符合出口條件
3. 方向擴展：對合法相鄰節點（非墻、未訪問）進行入隊
4. 終止條件：隊列為空時返回-1，表示無可行路徑

3. 復雜度

指標	值	說明
時間復雜度	O(mn)	最壞情況遍歷所有節點
空間復雜度	O(mn)	維護訪問數組和隊列的空間消耗

三、圖解示例

四、邊界條件與擴展

1. 特殊場景驗證

• 入口即出口：入口在邊界但不算出口，需尋找其他邊界點
• 全封閉迷宮：所有邊界點均為墻，返回-1
• 螺旋路徑：需繞行多層后到達邊界出口

2. 擴展應用

• 動態障礙物：支持實時更新墻的位置后重新計算路徑
• 多出口優化：尋找所有出口中的最近/最遠距離
• 三維迷宮：擴展為三維空間的路徑搜索問題

3. 其他語言

from collections import dequedef nearestExit(maze, entrance):m, n = len(maze), len(maze[0])directions = [(-1,0), (1,0), (0,-1), (0,1)]visited = [[False]*n for _ in range(m)]q = deque()# 初始化隊列和訪問狀態ent_r, ent_c = entranceq.append((ent_r, ent_c, 0))visited[ent_r][ent_c] = Truewhile q:r, c, steps = q.popleft()# 判斷當前節點是否為出口（邊界且非入口）if (r == 0 or r == m-1 or c == 0 or c == n-1) and (r, c) != (ent_r, ent_c):return steps# 遍歷四個方向for dr, dc in directions:nr, nc = r+dr, c+dcif 0 <= nr < m and 0 <= nc < n and not visited[nr][nc] and maze[nr][nc] == '.':visited[nr][nc] = Trueq.append((nr, nc, steps+1))return -1

五、總結與優化

1. 方法對比

方法	優勢	劣勢	適用場景
BFS	保證最短路徑	空間消耗較大	常規迷宮搜索
DFS	空間效率高	無法保證最短路徑	路徑存在性驗證
A*算法	啟發式搜索效率高	需設計啟發函數	大型迷宮優化搜索

2. 工程優化

• 雙向BFS：從入口和出口同時搜索，減少搜索空間
• 壓縮存儲：使用位運算壓縮訪問狀態數組
• 并行計算：對多個方向進行并行路徑探索

3. 算法擴展

• 權重迷宮：不同路徑消耗不同步數，尋找最小消耗路徑
• 移動模式：支持對角線移動或限定轉向次數
• 動態規劃：預處理各點到邊界的最短距離