Nearest Exit from Entrance in Maze — Medium Problem & Solution

Problem statement

A maze of m rows and n columns is given as maze, one string per row: '.' is an open cell and '+' is a wall. You stand at the open cell entrance = [row, col].

Each step moves you one cell up, down, left or right; you cannot enter a wall or leave the grid. An exit is any open cell on the outer border of the maze — except the entrance itself.

Return the number of steps on the shortest route from the entrance to the nearest exit, or -1 if no exit can be reached.

Example 1

Input: maze = ["+++++","+...+","+.+.+","+...+","++.++"], entrance = [1,1]
Output: 4
Explanation: The only exit is (4,2), reached via (2,1), (3,1) and (3,2).

Example 2

Input: maze = ["+.+","...","+.+"], entrance = [1,0]
Output: 2
Explanation: The entrance lies on the border but does not count; (0,1), (2,1) and (1,2) are each two steps away.

Example 3

Input: maze = [".+."], entrance = [0,0]
Output: -1

Constraints

• maze.length == m
• maze[i].length == n
• 1 <= m, n <= 100
• maze[i][j] is '.' or '+'
• entrance.length == 2
• 0 <= entrance[0] < m
• 0 <= entrance[1] < n
• entrance is an open cell

How to solve Nearest Exit from Entrance in Maze

Breadth-first search from the entrance explores cells in order of distance, so the first border cell it reaches is the nearest exit.

Approach

1. Mark the entrance visited and push it with distance 0.
2. Pop a cell; for each of its four neighbours that is inside the grid, open and unvisited:
3. if the neighbour lies on the border, return the current distance + 1; otherwise mark it and push it with distance + 1.
4. If the queue runs dry, return -1.

Why it works

BFS dequeues cells in non-decreasing distance order, and each neighbour is discovered at distance (parent + 1), which is its true shortest distance. Checking the exit condition at discovery time therefore returns the minimum over all exits. The entrance is visited from the start, so it can never be reported as an exit even when it sits on the border.

Complexity

• Time — O(m · n)
• Space — O(m · n)

Pitfalls

• An entrance on the border is not an exit — a check made when popping the start would wrongly return 0.
• Mark cells visited when they are pushed, not when popped, or the queue can hold the same cell many times.
• A 1 × 1 maze has no exit at all.

Reference solution

Python

from typing import List
from collections import deque

def nearestExit(maze: List[str], entrance: List[int]) -> int:
    m, n = len(maze), len(maze[0])
    seen = [[False] * n for _ in range(m)]
    sr, sc = entrance
    seen[sr][sc] = True
    q = deque([(sr, sc, 0)])
    while q:
        r, c, d = q.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc] and maze[nr][nc] == '.':
                if nr == 0 or nr == m - 1 or nc == 0 or nc == n - 1:
                    return d + 1
                seen[nr][nc] = True
                q.append((nr, nc, d + 1))
    return -1

JavaScript

var nearestExit = function(maze, entrance) {
    var m = maze.length, n = maze[0].length;
    var dist = [];
    for (var i = 0; i < m * n; i++) dist.push(-1);
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    var start = entrance[0] * n + entrance[1];
    dist[start] = 0;
    var queue = [start];
    for (var h = 0; h < queue.length; h++) {
        var r = Math.floor(queue[h] / n), c = queue[h] % n;
        for (var d = 0; d < 4; d++) {
            var nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || maze[nr][nc] !== '.') continue;
            var id = nr * n + nc;
            if (dist[id] !== -1) continue;
            dist[id] = dist[queue[h]] + 1;
            if (nr === 0 || nr === m - 1 || nc === 0 || nc === n - 1) return dist[id];
            queue.push(id);
        }
    }
    return -1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium