Beats 100% BFS Solution in Python with Explanation!
Approach: Breadth-First Search (BFS)Problem Breakdown
Given amazerepresented as a 2D grid, where:
.represents open paths.
+represents walls.


We start at a giv
### `Approach: Breadth-First Search (BFS)`

#### `Problem Breakdown`
- Given a `maze` represented as a 2D grid, where:
  - `.` represents open paths.
  - `+` represents walls.
- We start at a given `entrance` and must find the shortest path to the nearest exit.
- An exit is any open cell `.` on the boundary of the grid, except for the entrance itself.

---

### `Approach & Optimization`
1. `Use Breadth-First Search (BFS) for Shortest Path`
   - BFS is optimal for finding the shortest distance in unweighted graphs like this maze.
   - A `queue` is used to explore all possible moves level by level.

2. `Mark Cells as Visited In-Place`
   - Instead of using a `visited` set, mark visited cells directly in `maze` with `+`.
   - This saves `O(n * m)` space, making it more memory-efficient.

3. `Exit Detection`
   - If a new cell `(new_x, new_y)` is on the boundary and not the entrance, return the current `steps + 1`.

---

### `Time and Space Complexity`
- `Time Complexity: O(n * m)`
  - Each cell is processed at most once.
- `Space Complexity: O(n * m)`
  - The worst-case queue size stores all cells in the maze.

---

```python

from collections import deque
from typing import List

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        # Directions for moving in 4 possible ways (down, right, up, left)
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        
        rows, cols = len(maze), len(maze[0])
        x0, y0 = entrance
        
        # Use a queue for BFS with (row, col, steps)
        queue = deque([(x0, y0, 0)])
        maze[x0][y0] = '+'  # Mark entrance as visited to prevent re-visiting

        while queue:
            x, y, steps = queue.popleft()

            # Explore all four directions
            for dx, dy in directions:
                new_x, new_y = x + dx, y + dy

                if 0 <= new_x < rows and 0 <= new_y < cols and maze[new_x][new_y] == '.':
                    # If we reach an exit that is not the entrance
                    if new_x in [0, rows - 1] or new_y in [0, cols - 1]:
                        return steps + 1  
                    
                    # Mark cell as visited and add to queue
                    maze[new_x][new_y] = '+'
                    queue.append((new_x, new_y, steps + 1))

        return -1  # No exit found

```
['Python3']