Nearest Exit from Entrance in Maze

Problem in plain words

A maze is a grid where '.' is an open cell and '+' is a wall. You stand at a given entrance cell and can move up, down, left or right into open cells. An exit is any open cell on the outer border of the grid — but the entrance itself never counts as an exit. Return the fewest moves needed to reach an exit, or -1 if no exit is reachable.

Example: a 3 × 3 maze with walls everywhere except the middle row . . ., and the entrance at the middle cell (1, 1). One step left or right reaches a border cell, so the answer is 1.

Intuition

Every move costs the same, so the shortest path in moves is found by breadth-first search. BFS explores all cells 1 step away, then all cells 2 steps away, and so on. The first border cell it discovers is therefore the closest exit. Mark cells as visited when you enqueue them so nothing is processed twice.

Approach

1. Mark the entrance as visited (e.g. overwrite it with '+') and enqueue it with distance 0.
2. Pop a cell and try its four neighbours.
3. Skip neighbours that are outside the grid, walls, or already visited.
4. If a neighbour lies on the border, return the current distance + 1 — it is the nearest exit.
5. Otherwise mark it visited and enqueue it with distance + 1. If the queue empties, return -1.

Dry run

Maze rows: + + +, . . +, + . +, entrance (1, 1). Border open cells: (1, 0) and (2, 1).

The BFS would have found (1, 0) at the same distance; either exit gives 1.

Java solution

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        int rows = maze.length;
        int cols = maze[0].length;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {entrance[0], entrance[1], 0});
        maze[entrance[0]][entrance[1]] = '+';
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int r = cell[0] + d[0];
                int c = cell[1] + d[1];
                if (r < 0 || r >= rows || c < 0 || c >= cols || maze[r][c] != '.') {
                    continue;
                }
                if (r == 0 || r == rows - 1 || c == 0 || c == cols - 1) {
                    return cell[2] + 1;
                }
                maze[r][c] = '+';
                queue.offer(new int[] {r, c, cell[2] + 1});
            }
        }
        return -1;
    }
}

Python solution

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        rows, cols = len(maze), len(maze[0])
        sr, sc = entrance
        maze[sr][sc] = '+'
        queue = deque([(sr, sc, 0)])
        while queue:
            r, c, steps = queue.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] == '.':
                    if nr == 0 or nr == rows - 1 or nc == 0 or nc == cols - 1:
                        return steps + 1
                    maze[nr][nc] = '+'
                    queue.append((nr, nc, steps + 1))
        return -1

Complexity

Edge cases and common mistakes

• Counting the entrance as an exit — an entrance on the border is not an answer of 0. Marking it visited before the loop and only testing neighbours avoids this.
• Marking visited on pop — the same cell can then be queued several times; mark it when you enqueue it.
• Using DFS — DFS finds an exit, not necessarily the nearest one.
• Mutating the input — overwriting cells with '+' saves memory; use a separate visited array if the caller needs the maze intact.