Nearest Exit
Medium · Graphs · Array · Breadth-First Search · Matrix
Problem
You are given an m x n maze where '.' is an open cell and '+' is a wall, along with entrance = [row, col], the open cell where you start.
In one step you may move up, down, left or right into an open cell; you cannot walk through walls or leave the grid. An exit is any open cell on the 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.
Examples
Input: maze = [["+","+","+"],[".",".","+"],["+","+","+"]], entrance = [1,1] Output: 1
One step left reaches the open border cell (1,0).
Input: maze = [["+",".","+","+"],["+",".",".","+"],["+","+",".","+"]], entrance = [0,1] Output: 3
The entrance lies on the border but does not count, so the nearest exit is (2,2), three steps away.
Input: maze = [[".","+"]], entrance = [0,0] Output: -1
The only open cell is the entrance, which is not an exit.
Constraints
- maze.length == m, maze[i].length == n
- 1 <= m, n <= 100
- maze[i][j] is '.' or '+'
- entrance.length == 2
- entrance is an open cell inside the grid
Approaches
- Relax distances until nothing changes — time O((m · n)²), space O(m · n)
Follow-up
If you could break through one wall on the way, the state becomes (cell, walls broken), and the same BFS runs on twice as many states. With many entrances and one question per entrance, a single multi-source BFS from all exits answers every entrance at once.
Related problems
Start free on Cariara · Coding problems · System design studio
