題目描述:給定 m × n 的迷宮矩陣,. 代表空格,+ 代表牆壁。給定起點 entrance(位於空格),求從起點到最近出口的最短步數。出口定義為位於邊界且不是起點本身的空格。若無法到達任何出口,回傳 -1。
解題思路:BFS 是求最短路徑的標準方法。將起點加入佇列,每次擴展一層(步數加一),遇到邊界空格即為出口立即回傳當前步數。將訪問過的格子標記為 + 以避免重複訪問。BFS 保證第一次到達出口時的步數即為最短步數。
時間複雜度:O(m × n) — 每個格子最多被加入佇列一次。
空間複雜度:O(m × n) — BFS 佇列最壞情況下存放所有格子。
1. Push entrance into queue; mark entrance as visited ('+')
2. steps = 0
3. While queue is not empty:
a. steps++
b. For each node in current BFS layer:
- Dequeue (r, c)
- For each of 4 directions (nr, nc):
* Skip if out of bounds or wall
* If (nr, nc) is on boundary: return steps
* Mark (nr, nc) as visited, enqueue it
4. Return -1DFS + 全域最短距離 O(m×n):DFS 遍歷所有可達路徑並記錄到達出口的最小步數。但 DFS 不保證最短路徑優先,需遍歷所有路徑才能確認最短,效率劣於 BFS。
Dijkstra O(m×n log(m×n)):本題邊權皆為 1,Dijkstra 退化為 BFS,額外的優先佇列開銷不必要。僅在邊權不同時才值得使用 Dijkstra。