✅Beats 100% | ✅BFS Solution | C++
🚀 Nearest Exit in a Maze🧠 IntuitionThe problem asks us to find the shortest path from a given entrance to any exit in the maze. Since we're looking for the shor
# 🚀 Nearest Exit in a Maze

## 🧠 Intuition
The problem asks us to find the shortest path from a given entrance to any exit in the maze. Since we're looking for the shortest path, we can apply **Breadth-First Search (BFS)**. 

- **BFS** ensures that we explore all possible paths level by level, and the first exit we encounter will be the nearest one.
- We track the visited cells to avoid revisiting them, which would otherwise result in unnecessary computations.
- The key observation is that any exit lies on the boundary of the maze, and we can return the first such boundary cell we encounter during BFS.

## 🛠️ Approach
1. **Initialization**:
   - Start by marking the entrance as visited.
   - Use a queue to explore the maze, starting from the entrance.
   - Maintain a set of directions (up, down, left, right) for BFS traversal.
   
2. **BFS Traversal**:
   - Explore the maze using BFS.
   - For each cell, if it is an exit (a boundary cell), return the distance from the entrance.
   - Mark each cell as visited before adding it to the queue to avoid cycles.

3. **Exit Conditions**:
   - If a boundary cell is reached, and it is not the entrance, return the distance.
   - If no exit is found, return `-1`.

## ⏳ Complexity

- **Time Complexity**: **O(m × n)**  
  - Each cell is visited at most once, so BFS runs in linear time with respect to the number of cells in the maze.
  
- **Space Complexity**: **O(m × n)**  
  - The space complexity is dominated by the queue and the visited array, both of which store the state of each cell.

## 💻 Code

```cpp
class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size();
        int n = maze[0].size();
        vector<vector<int>> vis(m, vector<int>(n, 0));
        vis[entrance[0]][entrance[1]] = 1;
        queue<pair<int, int>> q;
        q.push({entrance[0], entrance[1]});

        vector<pair<int, int>> dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

        int ans = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                auto top = q.front();
                q.pop();

                for (int k = 0; k < 4; k++) {
                    int r = top.first + dir[k].first;
                    int c = top.second + dir[k].second;
                    if (r < 0 || c < 0 || r >= m || c >= n || vis[r][c] ||
                        maze[r][c] == '+')
                        continue;
                    else if (r == 0 || c == 0 || r == m - 1 || c == n - 1)
                        return ans + 1;
                    q.push({r, c});
                    vis[r][c] = 1;
                }
            }
            ans++;
        }
        return -1;
    }
};

['C++']