Show problems as
Classic problem #1926MediumArrayBreadth-First SearchMatrix

Nearest Exit from Entrance in Maze

Real-world version: The Nearest Way Out of the Vault
Tracked in this browser only
Read Nearest Exit from Entrance in Maze on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A vault floor is given as the grid vault, where '.' marks an open cell and '+' marks a wall. A step moves to a cell sharing an edge with the current one, and only open cells may be stood on.

You start on the open cell at row start[0] and column start[1]. An exit is any open cell on the outer edge of the grid other than the cell you start on.

Return the fewest steps needed to reach an exit, or -1 when no exit can be reached.

Examples

Example 1

Input
vault = [[".", ".", "."], [".", "+", "."], [".", ".", "."]], start = [1, 0]
Output
1

The starting cell sits on the left edge, but it cannot count as its own exit. The cell straight above it is open and also on the edge, so one step is enough.

Example 2

Input
vault = [["+", "+", "+"], ["+", ".", "+"], ["+", "+", "+"]], start = [1, 1]
Output
-1

The only open cell is walled in on all four sides, so no exit can be reached.

Example 3

Input
vault = [["+", "+", "+", "+", "+"], ["+", ".", ".", ".", "."], ["+", ".", "+", "+", "+"], ["+", ".", "+", "+", "+"], ["+", ".", "+", "+", "+"]], start = [1, 1]
Output
3

Two exits are reachable: the open cell at the right end of the second row and the one at the bottom of the second column. Both lie three steps away.

Constraints

  • 1 <= vault.length <= 100
  • 1 <= vault[i].length <= 100
  • Every cell of vault is a full stop or a plus sign.
  • start.length == 2
  • 0 <= start[0] <= vault.length - 1
  • The cell you start on is open.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def nearest_exit(vault: list[list[str]], start: list[int]) -> int:
Java
public int nearestExit(char[][] vault, int[] start)

More on the same topics