1926. Nearest Exit from Entrance in Maze

Problem¶

Given a maze of open cells . and walls +, return the fewest four-directional steps from entrance to any open border cell other than the entrance. Return -1 if none is reachable.

maze = [
  ["+", "+", ".", "+"],
  [".", ".", ".", "+"],
  ["+", "+", "+", "."]
]
entrance = [1, 2] -> 1

Key trick¶

Use BFS because it visits reachable cells in increasing distance order; the first discovered border cell is therefore the nearest exit.

Trap¶

Do not count the entrance as an exit when it lies on the border.
Mark cells visited when enqueuing them, not when dequeuing them.
Avoid revisiting open cells, which can cause duplicate work or cycles.
In-place marking mutates the input maze.

Why is it interesting?¶

It tests recognizing an unweighted grid as a graph and using BFS to guarantee a shortest path while handling a subtle entrance exception.

Python solution¶

from collections import deque


class Solution:
    def nearestExit(self, maze: list[list[str]], entrance: list[int]) -> int:
        m, n = len(maze), len(maze[0])
        start_r, start_c = entrance
        q = deque([(start_r, start_c, 0)])

        # Reuse the maze as the visited set.
        maze[start_r][start_c] = "+"

        while q:
            r, c, steps = q.popleft()

            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr, nc = r + dr, c + dc

                if not (0 <= nr < m and 0 <= nc < n):
                    continue
                if maze[nr][nc] == "+":
                    continue

                # Any discovered border cell is not the entrance.
                if nr in (0, m - 1) or nc in (0, n - 1):
                    return steps + 1

                maze[nr][nc] = "+"
                q.append((nr, nc, steps + 1))

        return -1

Time complexity: \(O(mn)\).

Space complexity: \(O(mn)\) in the worst case for the BFS queue.

Comment on my solution¶

Your solution is correct and has optimal \(O(mn)\) time and \(O(mn)\) worst-case queue space.

The BFS ordering guarantees the returned distance is minimal.
Marking cells when enqueuing correctly prevents duplicate visits.
Detecting an exit by noticing that the current cell has an out-of-bounds neighbor works, and step != 0 excludes the entrance.
Checking whether a newly reached cell is on the border is more direct and avoids representing an exit indirectly as an attempted move outside the maze.
The implementation mutates maze, which is space-efficient but should be noted if callers expect the input to remain unchanged.

from collections import deque

# Ideas:
# - classic BFS on a grid with in-place marking cell with + when visited
class Solution:
    def nearestExit(self, maze: list[list[str]], entrance: list[int]) -> int:
        m, n = len(maze), len(maze[0])
        q = deque([(*entrance, 0)]) # (row, col, step)
        # mark entrance as visited in maze
        maze[entrance[0]][entrance[1]] = "+"

        while q:
            r, c, step = q.popleft()
            for dr, dc in ((-1,0), (1,0), (0,-1), (0,1)):
                nr, nc = r + dr, c + dc
                if nr < 0 or nr >= m or nc < 0 or nc >= n:
                    if step != 0:
                        return step
                    else:
                        continue
                elif maze[nr][nc] == "+":
                    continue
                else:
                    maze[nr][nc] = "+"
                    q.append((nr, nc, step + 1))

        return -1