1926. Nearest Exit from Entrance in Maze

📘 題目敘述

給你一個 m x n 的矩陣 maze（0-indexed），其中空格用 '.' 表示、牆壁用 '+' 表示。你也會拿到迷宮的入口 entrance，其中 entrance = [entrance_row, entrance_col] 代表你一開始站的位置（行、列）。

每一步你可以往上、下、左、右移動一格。你不能走到牆壁，也不能走出迷宮。

你的目標是從 entrance 找到最近的出口。出口定義為：在迷宮邊界上的空格（第一/最後一列或第一/最後一行）。注意：入口本身不算出口。

請回傳從入口到最近出口的最短路徑步數；如果不存在這種路徑，回傳 -1。

條件限制

• maze.length == m
• maze[i].length == n
• 1 <= m, n <= 100
• maze[i][j] 只會是 '.' 或 '+'
• entrance.length == 2
• 0 <= entrance_row < m
• 0 <= entrance_col < n
• entrance 一定會是一個空格

🧠 解題思路

我這題用 BFS，因為題目要的是「最短步數」，而迷宮每一步移動的成本都一樣（走一格就是 +1 步），所以 BFS 一層一層擴展，第一次走到出口時，就一定是最短距離。

我的寫法用兩個 queue<int> 分別存 x / y 座標，搭配 dx/dy 代表四個方向位移。

另外我把走過的格子直接改成 '+'，等於「把它當牆」，避免重複走回來造成無限循環，也省掉額外 visited 陣列。

所有變數

• count：目前 BFS 走到第幾步（第幾層）。我每處理完一層就讓它 +1，所以當我找到出口時，count 就是最短步數
• m：迷宮列數
• n：迷宮行數
• x：BFS 用的 queue，存目前所有待處理格子的 row
• y：BFS 用的 queue，存目前所有待處理格子的 col
• dx、dy：四方向位移（下、上、右、左），用來快速枚舉鄰居

🪜 主要流程步驟

1. 初始化 BFS 起點，並把入口標記成已走過

我先把入口 (entrance[0], entrance[1]) 放進 x / y 兩個 queue。然後直接做 maze[entrance[0]][entrance[1]] = '+'，表示入口已經走過，避免之後又走回入口。

2. 一層一層 BFS，count 代表目前步數

只要 queue 還有東西，就代表還有位置可以擴展。每次外層 while 開始，我先記錄這一層有多少個點 s = x.size()，並把 count++，表示接下來這一層的擴展是「走了第 count 步」才到的新格子。

3. 對每個當前格子，往四個方向嘗試走一步

我用 dx/dy 算出鄰居 (nx, ny)：

• 如果 (nx, ny) 超出邊界：直接略過
• 如果 maze[nx][ny] == '.'：代表可走
  • 如果這個鄰居在邊界上（nx==0 或 nx==m-1 或 ny==0 或 ny==n-1），那它就是出口，直接回傳 count
  • 否則把它標記成 '+'，並 push 進 queue，等下一層繼續擴展

4. BFS 結束還沒找到出口，就回傳 -1

如果 queue 都清空了，代表所有能到的空格都走遍了仍然沒有出口路徑，所以答案是 -1。

⏱️ 複雜度

• 時間複雜度：O(mn)，每個格子最多進 queue 一次、每次最多看 4 個方向
• 空間複雜度：O(mn)，最壞情況 queue 可能同時存很多格子（加上原地標記不另外開 visited）

💻 程式碼實作

class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int count = 0;
        int m = maze.size(), n = maze[0].size();
        queue<int> x, y;
        x.push(entrance[0]), y.push(entrance[1]);
        int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
        maze[entrance[0]][entrance[1]] = '+';
        while (!x.empty()) {
            int s = x.size();
            count++;
            for (int j = 0; j < s; j++) {
                for (int i = 0; i < 4; i++) {
                    int nx = x.front() + dx[i], ny = y.front() + dy[i];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                        continue;
                    } else if (maze[nx][ny] == '.') {
                        if (nx == 0 || nx == m - 1 || ny == 0 || ny == n - 1) {
                            return count;
                        }
                        maze[nx][ny] = '+';
                        x.push(nx);
                        y.push(ny);
                    }
                }
                x.pop();
                y.pop();
            }
        }
        return -1;
    }
};

🔗 題目連結

https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/