---
# System prepended metadata

title: Nearest Exit from Entrance in Maze
tags: ["medium\_"]

---

# Nearest Exit from Entrance in Maze
這題我有先試著自己寫一次，但是差一點，給gpt debug 才搞出來的，

他的做法是用queue，先放入起點，然後移動有上下左右，如果不是碰到橋的邊緣(達成條件)，就會繼續放入queue，如果達成條件返還step，因為一定是最小的
```
class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int row = maze.size();
        int col = maze[0].size();
        int entR = entrance[0], entC = entrance[1];
        
        // 方向：下、上、右、左
        vector<pair<int,int>> dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        
        queue<pair<int,int>> q;
        q.push({entR, entC});
        maze[entR][entC] = '+';  // 標記起點已訪
        
        int steps = 0;
        while (!q.empty()) {
            int sz = q.size();
            // 一層一層跑
            while (sz--) {
                auto [r, c] = q.front(); 
                q.pop();
                
                // 到達出口（排除起點）
                if (!(r == entR && c == entC) &&
                    (r==0 || r==row-1 || c==0 || c==col-1)) {
                    return steps;
                }
                
                // 四個方向
                for (auto [dr, dc] : dirs) {
                    int nr = r + dr, nc = c + dc;
                    // 邊界 & 只走未訪且是空地
                    if (nr < 0 || nr >= row || nc < 0 || nc >= col) 
                        continue;
                    if (maze[nr][nc] != '.') 
                        continue;
                    
                    maze[nr][nc] = '+';  // 標記已訪
                    q.push({nr, nc});
                }
            }
            steps++;  // 換下一層
        }
        
        return -1;  // 無法到任何出口
    }
};

```