Nearest Maze Exit

Medium

A maze is given as a table grid with m rows and n columns: . is an open cell and + is a wall. You stand on the open cell start = [row, column] (0-based). In one step you can move to the neighboring cell above, below, left or right, as long as it is not a wall and is inside the table. An exit is any open cell on the edge of the table, other than the start. Return the fewest steps needed to reach some exit, or -1 if no exit can be reached.

Example 1

grid=[["+", "+", "+", "+"], [".", ".", ".", "+"], ["+", "+", ".", "+"], ["+", "+", ".", "+"]], start=[1, 2] → 2

There are two exits: cell [1, 0], two steps left, and cell [3, 2], two steps down. The nearest one is 2 steps away.

Example 2

grid=[[".", ".", "."]], start=[0, 1] → 1

Every cell is on the edge, so a neighboring cell is already an exit.

Example 3

grid=[["+", "+"], [".", "+"]], start=[1, 0] → -1

The only open cell is the start itself, and the start does not count as an exit.

Constraints

1 ≤ m, n ≤ 100
Every cell is . or +
start is an open cell inside the table

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Array Matrix

Similar problems

Drain the Landlocked Ponds Medium Land Regions on a Map Medium Steps to the Nearest Exit Medium Rain Reaching Both Seas Medium Can the Ball Stop at the Target Medium

Input

grid=[["+", "+", "+", "+"], [".", ".", ".", "+"], ["+", "+", ".", "+"], ["+", "+", ".", "+"]], start=[1, 2]

Expected

Run checks the first 3 tests in your browser. Submit checks all 10 tests on the server, hidden ones included.