# Nearest Exit from Entrance in Maze
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/nearest-exit-from-entrance-in-maze)
Canonical: https://scaleengineer.com/dsa/problems/nearest-exit-from-entrance-in-maze
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung), [eBay](https://scaleengineer.com/companies/ebay)
---
## Problem
You are given an `m x n` matrix `maze` (**0-indexed**) with empty cells (represented as `'.'`) and walls (represented as `'+'`). You are also given the `entrance` of the maze, where `entrance = [entrancerow, entrancecol]` denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell **up**, **down**, **left**, or **right**. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the **nearest exit** from the `entrance`. An **exit** is defined as an **empty cell** that is at the **border** of the `maze`. The `entrance` **does not count** as an exit.

Return _the **number of steps** in the shortest path from the_ `entrance` _to the nearest exit, or_ `-1` _if no such path exists_.

**Example 1:**

![](https://assets.glich.co/dsa/nearest-exit-from-entrance-in-maze/image0.jpg) 

**Input:** maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
**Output:** 1
**Explanation:** There are 3 exits in this maze at [1,0], [0,2], and [2,3].
Initially, you are at the entrance cell [1,2].
- You can reach [1,0] by moving 2 steps left.
- You can reach [0,2] by moving 1 step up.
It is impossible to reach [2,3] from the entrance.
Thus, the nearest exit is [0,2], which is 1 step away.

**Example 2:**

![](https://assets.glich.co/dsa/nearest-exit-from-entrance-in-maze/image1.jpg) 

**Input:** maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
**Output:** 2
**Explanation:** There is 1 exit in this maze at [1,2].
[1,0] does not count as an exit since it is the entrance cell.
Initially, you are at the entrance cell [1,0].
- You can reach [1,2] by moving 2 steps right.
Thus, the nearest exit is [1,2], which is 2 steps away.

**Example 3:**

![](https://assets.glich.co/dsa/nearest-exit-from-entrance-in-maze/image2.jpg) 

**Input:** maze = [[".","+"]], entrance = [0,0]
**Output:** -1
**Explanation:** There are no exits in this maze.

**Constraints:**

* `maze.length == m`
* `maze[i].length == n`
* `1 <= m, n <= 100`
* `maze[i][j]` is either `'.'` or `'+'`.
* `entrance.length == 2`
* `0 <= entrancerow < m`
* `0 <= entrancecol < n`
* `entrance` will always be an empty cell.

# Approaches
## Brute-Force Depth-First Search
This approach uses Depth-First Search (DFS) to exhaustively explore all possible paths from the entrance. It keeps track of the minimum number of steps required to reach any exit cell. Because DFS explores as deeply as possible along one path before backtracking, it does not guarantee that the first exit found is the nearest one. Therefore, it must potentially explore a vast number of paths to find the true minimum, making it highly inefficient for this problem.
**Time:** O(3^(m*n)) in the worst case. From any given cell, there are at most 3 new directions to explore. The algorithm might explore all simple paths, leading to an exponential runtime. · **Space:** O(m * n) for the recursion stack in the worst case (a path that visits every cell) and the `visited` matrix.
**Pros:** Conceptually simple if familiar with recursion and graph traversal.
**Cons:** Extremely inefficient for this problem, as it's not designed to find the shortest path directly.; Time complexity can be exponential in the worst case, leading to a 'Time Limit Exceeded' error on larger mazes.; Prone to stack overflow errors for mazes with very long paths due to deep recursion.
### Explanation
The core of this method is a recursive function that explores the maze. We maintain a `visited` array to prevent getting stuck in cycles within a single path exploration. A global variable, `minSteps`, stores the length of the shortest path found so far.

The search starts at the `entrance`. For each cell, the function checks if it's a valid move. If the cell is an exit (a border cell that is not the entrance), we compare its path length (`steps`) with `minSteps` and update it if the new path is shorter. A key part of this brute-force DFS is backtracking: after exploring from a cell, we must unmark it as visited so that other potential paths can use it. This exhaustive search ensures we check all possibilities but at a very high computational cost.

```java
class Solution {
    int minSteps = Integer.MAX_VALUE;

    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length;
        int n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        dfs(entrance[0], entrance[1], 0, maze, visited, entrance);
        return minSteps == Integer.MAX_VALUE ? -1 : minSteps;
    }

    private void dfs(int r, int c, int steps, char[][] maze, boolean[][] visited, int[] entrance) {
        // Check if out of bounds, a wall, or already visited in the current path
        if (r < 0 || r >= maze.length || c < 0 || c >= maze[0].length || maze[r][c] == '+' || visited[r][c]) {
            return;
        }

        // Check if it's an exit (and not the entrance cell)
        boolean isEntrance = (r == entrance[0] && c == entrance[1]);
        if (!isEntrance && (r == 0 || r == maze.length - 1 || c == 0 || c == maze[0].length - 1)) {
            minSteps = Math.min(minSteps, steps);
            // We found an exit, but must continue searching for a potentially shorter path.
            // Returning here would be incorrect as another path to another exit might be shorter.
        }

        // Pruning: if current steps are already not better than the best found so far, stop.
        if (steps >= minSteps) {
            return;
        }

        visited[r][c] = true;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        for (int i = 0; i < 4; i++) {
            dfs(r + dr[i], c + dc[i], steps + 1, maze, visited, entrance);
        }

        visited[r][c] = false; // Backtrack to allow other paths to use this cell
    }
}
```
### Algorithm
- Initialize a global variable `minSteps` to infinity.
- Create a `visited` boolean matrix to keep track of cells visited in the current path to avoid cycles.
- Define a recursive function `dfs(row, col, steps)`.
- Start the search from the entrance: `dfs(entrance_row, entrance_col, 0)`.
- In the `dfs` function:
  - If the current cell is out of bounds, a wall, or already visited in the current path, return.
  - If the current path's length (`steps`) is already greater than or equal to `minSteps`, prune this path and return.
  - If the current cell is an exit (on the border and not the entrance), update `minSteps = min(minSteps, steps)`.
  - Mark the current cell as visited.
  - Recursively call `dfs` for all four neighbors (up, down, left, right), incrementing `steps`.
  - Backtrack by unmarking the current cell as visited. This is crucial to allow other paths to explore this cell.
- After the initial `dfs` call completes, if `minSteps` is still infinity, no exit was reachable. Return -1. Otherwise, return `minSteps`.

## Breadth-First Search (BFS)
This problem asks for the shortest path in a maze where each step has an equal cost, which is a classic use case for Breadth-First Search (BFS). BFS explores the maze layer by layer from the starting point. This guarantees that the first time we reach an exit cell, we have found a path with the minimum number of steps. Any other path to this exit or any other exit would be at least as long.
**Time:** O(m * n), where `m` and `n` are the dimensions of the maze. Every empty cell is enqueued and dequeued at most once. · **Space:** O(m * n) in the worst case. The space is used by the queue, which can hold a number of cells proportional to the width of the maze.
**Pros:** Optimal and efficient, as it guarantees finding the shortest path.; Visits each cell at most once, resulting in a linear time complexity.
**Cons:** Uses extra space for the queue, which can be up to O(m * n) in the worst case.; If the implementation modifies the input grid to mark visited cells, it might be an undesirable side effect.
### Explanation
We can model the maze as an unweighted graph where each empty cell is a node and adjacent empty cells are connected by an edge. The BFS algorithm is perfect for finding the shortest path from a single source in such a graph.

We start by placing the `entrance` cell into a queue. We also need a way to keep track of visited cells to avoid infinite loops and redundant computations; this can be done with a separate `boolean[][]` array or by modifying the input `maze` in-place (e.g., changing visited `.` to `+`).

The search proceeds in levels. We maintain a `steps` counter. In each step of the BFS, we dequeue all the cells that are at the current distance (`steps - 1`) and enqueue all their valid, unvisited neighbors. These new neighbors are at distance `steps`. Before adding a neighbor to the queue, we check if it's an exit (an empty cell on the border). Since BFS explores level by level, the first exit we encounter is guaranteed to be the nearest one. We can immediately return the current `steps` count. If the queue becomes empty before an exit is found, it means no exit is reachable.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length;
        int n = maze[0].length;

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(entrance);
        // Mark the entrance as visited to avoid revisiting it.
        // Modifying the input is a common trick to save space.
        maze[entrance[0]][entrance[1]] = '+';

        int steps = 0;
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            steps++;

            for (int i = 0; i < levelSize; i++) {
                int[] current = queue.poll();
                int r = current[0];
                int c = current[1];

                // Explore neighbors
                for (int[] dir : dirs) {
                    int newR = r + dir[0];
                    int newC = c + dir[1];

                    // Check if the new cell is out of bounds
                    if (newR < 0 || newR >= m || newC < 0 || newC >= n) {
                        continue;
                    }

                    // Check if the new cell is a wall (or already visited)
                    if (maze[newR][newC] == '+') {
                        continue;
                    }

                    // If we found a valid path to a border cell, it's an exit.
                    // Since this is BFS, this is the shortest path.
                    if (newR == 0 || newR == m - 1 || newC == 0 || newC == n - 1) {
                        return steps;
                    }

                    // Mark as visited and add to the queue for the next level
                    maze[newR][newC] = '+';
                    queue.offer(new int[]{newR, newC});
                }
            }
        }

        // If the queue becomes empty, no path to an exit exists.
        return -1;
    }
}
```
### Algorithm
- Get the maze dimensions `m` and `n`.
- Initialize a queue and add the `entrance` coordinates to it.
- Mark the `entrance` cell as visited to prevent cycles. A common way is to modify the input grid, e.g., `maze[entrance_row][entrance_col] = '+'`.
- Initialize a `steps` counter to 0.
- Start a loop that continues as long as the queue is not empty.
- In each iteration, process all nodes at the current level. Get the `levelSize` of the queue.
- Increment `steps`. This new value represents the distance to the next level of cells.
- Loop `levelSize` times to process each cell at the current distance.
  - Dequeue a cell `(r, c)`.
  - Explore its four neighbors `(nr, nc)`.
  - For each neighbor, check if it's valid (within bounds and not a wall).
  - If a valid neighbor is on the border, it's the nearest exit. Return the current `steps`.
  - If a valid neighbor is not an exit, mark it as visited and enqueue it for processing in the next level.
- If the queue becomes empty and no exit was found, return -1.

# Solutions
### Java

```java
class Solution {
public
  int nearestExit(char[][] maze, int[] entrance) {
    int m = maze.length;
    int n = maze[0].length;
    Deque<int[]> q = new ArrayDeque<>();
    q.offer(entrance);
    maze[entrance[0]][entrance[1]] = '+';
    int ans = 0;
    int[] dirs = {-1, 0, 1, 0, -1};
    while (!q.isEmpty()) {
      ++ans;
      for (int k = q.size(); k > 0; --k) {
        int[] p = q.poll();
        int i = p[0], j = p[1];
        for (int l = 0; l < 4; ++l) {
          int x = i + dirs[l], y = j + dirs[l + 1];
          if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.') {
            if (x == 0 || x == m - 1 || y == 0 || y == n - 1) {
              return ans;
            }
            q.offer(new int[]{x, y});
            maze[x][y] = '+';
          }
        }
      }
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int nearestExit(vector<vector<char>> &maze, vector<int> &entrance) {
    int m = maze.size(), n = maze[0].size();
    queue<vector<int>> q{{entrance}};
    maze[entrance[0]][entrance[1]] = '+';
    int ans = 0;
    vector<int> dirs = {-1, 0, 1, 0, -1};
    while (!q.empty()) {
      ++ans;
      for (int k = q.size(); k > 0; --k) {
        auto p = q.front();
        q.pop();
        for (int l = 0; l < 4; ++l) {
          int x = p[0] + dirs[l], y = p[1] + dirs[l + 1];
          if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.') {
            if (x == 0 || x == m - 1 || y == 0 || y == n - 1)
              return ans;
            q.push({x, y});
            maze[x][y] = '+';
          }
        }
      }
    }
    return -1;
  }
};

```

### Python

```python
class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int: m, n = len(maze), len(maze[0]) i, j = entrance q = deque([(i, j)]) maze[i][j] = '+' ans = 0 while q: ans += 1 for _ in range(len(q)): i, j = q . popleft() for a, b in [[0, - 1], [0, 1], [- 1, 0], [1, 0]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and maze[x][y] == '.': if x == 0 or x == m - 1 or y == 0 or y == n - 1: return ans q . append((x, y)) maze[x][y] = '+' return - 1

```