Problem 21.5 · Breadth-First SearchMedium

Nearest Exit from Entrance in Maze

What it teaches: Grid BFS with a goal test on the border (and the entrance excluded).

Practise it on judges as “Nearest Exit from Entrance in Maze”.

The problem

A maze has '.' for open cells and '+' for walls. From entrance = [row, col], return the fewest steps to any open cell on the border (an exit). The entrance itself doesn't count as an exit. Return −1 if there is none.

Example 1

Input: maze = [[+,+,.,+],[.,.,.,+],[+,+,+,.]], entrance = [1,2]
Output: 1

Constraints

1 ≤ rows, cols ≤ 100

Pattern clues in the wording

→ Fewest steps on a grid to any of several targets

These clues point to Graph BFS: Explore from a start node in rings of increasing distance using a queue and a visited set.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        return -1;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]] entrance = [1,2]	1
2	maze = [["+","+","+"],[".",".","."],["+","+","+"]] entrance = [1,0]	2
3	maze = [[".","+"]] entrance = [0,0]	-1

From slow to fast

Approaches

1. BFS with level count · O(rows × cols)

BFS with level count

Time O(rows × cols) Space O(rows × cols)

Level-order BFS. When popping a border cell that isn't the entrance, return the level.

Approach 1

import java.util.*;

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length, n = maze[0].length;
        boolean[][] seen = new boolean[m][n];
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(entrance);
        seen[entrance[0]][entrance[1]] = true;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int steps = 0; !q.isEmpty(); steps++) {
            for (int size = q.size(); size > 0; size--) {
                int[] cell = q.poll();
                int r = cell[0], c = cell[1];
                boolean border = r == 0 || c == 0 || r == m - 1 || c == n - 1;
                if (border && steps > 0) return steps;
                for (int[] d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr < 0 || nc < 0 || nr >= m || nc >= n || seen[nr][nc] || maze[nr][nc] == '+') continue;
                    seen[nr][nc] = true;
                    q.offer(new int[]{nr, nc});
                }
            }
        }
        return -1;
    }
}

Verdict: Standard.

Before you submit

Edge cases and common mistakes

Test these inputs

Entrance on the border
1 × 1 maze
No exit reachable

Mistakes people make

Returning 0 because the entrance is on the border.

Interview

Follow-up questions

How do you return the path, not just its length?

Command Palette

The problem

Approaches

BFS with level count

Edge cases and common mistakes

Follow-up questions