Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Nearest Exit from Entrance in Maze (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

You are given a maze of size m x n as a 2D grid with walls and open spaces. The walls are marked as '+', and the open spaces are marked as '.'. You also have an entrance point of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.

You can start the movement from the entrance, and in a single step, you can move up, down, left, or right into another open space. You can't move to the cell having a wall or outside of the maze.

Find the shortest path from the entrance to any exit. An exit is an open space at the border of the maze. Note that the entrance is not considered an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit. If there is no way to reach an exit, return -1.

Examples

Example 1

  • Input: entrance = [1,2], maze =
[["+","+","+","+"],
 [".",".",".","+"],
 [".",".","+","."]]
  • Expected Output: 2
Image
  • Explanation: Starting at (1,2), you can move to (1,1), and from (1, 1), you can either move to (1, 0) or (2, 1), which is an exit.

Example 2

  • Input: entrance = [0,0], maze =
[[".",".",".","+"],
 ["+","+",".","+"],
 ["+","+","+","."],
 ["+","+","+","."]]

  • Expected Output: 1
Image
  • Explanation: Starting at (0,0), you move to (1,0), reaching an exit at the bottom border.

Example 2

  • Input: entrance = [0,2], maze =
[["+","+",".","+"],
 ["+","+","+","."]]
  • Expected Output: -1
  • Explanation: The entrance is already at the border but does not count as an exit, and there are no other reachable exits.

Constraints:

  • maze.length == m
  • maze[i].length == n
  • 1 <= m, n <= 100
  • maze[i][j] is either '.' or '+'.
  • entrance.length == 2
  • 0 <= entrancerow < m
  • 0 <= entrancecol < n
  • entrance will always be an empty cell.

Try it yourself

Try solving this question here:

Python3
Python3

. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible