Nearest Exit From Maze
MediumGraph · Uber
You are given a maze as a list of equal-length strings board, where "." is an open cell and "+" is a wall, and an open starting cell start = [row, col].
In one step you can move up, down, left, or right into an adjacent open cell. You cannot enter walls or leave the grid.
An exit is any open cell on the border of the grid (first or last row, or first or last column). The starting cell never counts as an exit, even if it is on the border.
Return the minimum number of steps needed to reach an exit from start, or -1 if no exit is reachable.
Example 1
- Input:
- board = ["++.++", "+...+", "+.+.+", "+....", "+++++"], start = [2, 1]
- Output:
- 3
- Explanation
- From
[2, 1]you can go up to[1, 1], right to[1, 2], then up to the border cell[0, 2]in 3 steps. The other exit[3, 4]needs 4 steps (down, then right three times).
Example 2
- Input:
- board = ["+.+", "...", "+++"], start = [1, 0]
- Output:
- 2
- Explanation
- The start is on the left border but does not count. Both
[0, 1]and[1, 2]are exits 2 steps away.
Example 3
- Input:
- board = ["+++", "+.+", "+++"], start = [1, 1]
- Output:
- -1
- Explanation
- Every neighbor of the start is a wall, so no exit can be reached.
Constraints
1 <= board.length, board[i].length <= 100- All rows of
boardhave the same length board[i][j]is"."or"+"start = [row, col]is inside the grid andboard[row][col] == "."