Maze Nearest Exit

Problem

Given a maze of dot and plus characters and an entrance cell, return the number of steps to the nearest exit, where an exit is any dot on the border other than the entrance, or -1 if none is reachable.

Run BFS from the entrance and test for the border when expanding each neighbour. The entrance itself never counts as an exit.

Hint

An exit is discovered while expanding a neighbour, so the current layer count is the distance.

Test cases

case 1

in: [[["+","+",".","+"],[".",".",".","+"],["+","+","+","."]],[1,2]]

expected: 1

case 2

in: [[["+","+",".","+"],[".",".",".","+"],["+","+","+","."]],[0,2]]

expected: 3

case 3

in: [[[".","+"]],[0,0]]

expected: -1

case 4

in: [[["."]],[0,0]]

expected: -1

case 5

in: [[["+","+","+"],["+",".","+"],["+","+","+"]],[1,1]]

expected: -1

Starter codePython

def nearest_exit(maze, entrance):
    # Your code here
    pass

5 test cases · run your code against them in the editor