Shortest path in a mazeMedium
Let's say you're given a maze as a binary matrix made up of 1s and 0s, along with start and end coordinates.
maze = [[1, 1, 1, 1],[1, 0, 0, 1],[1, 1, 1, 1],[0, 1, 0, 0],]start = (0, 0)end = (3, 1)
A path can be formed only along cells with
0represents an obstacle that cannot be part of a path.
Assume you can move in 4 directions -- left, right, up, and down.
Write a function that returns the distance of the shortest path from the start to the end coordinate.
For example, given the above inputs, your function should return
4as highlighted by the following path:
Before you look at the solution, try to code it yourself.
Time and Space Complexity
In breadth first search, we visit all edges and vertizes.
Therefore, our time complexity is
O(V + E).