Grid Shortest Path with Obstacles

Problem

Find the length of the shortest path from the top-left to the bottom-right cell of a grid, moving up, down, left, or right.

grid contains 0 for free cells and 1 for obstacles. Return the number of moves, or -1 when no path exists. A 1x1 free grid needs 0 moves.

Hint

BFS over free cells gives the fewest moves in an unweighted grid.

case 1

in: [[[0,0,1],[0,1,0],[0,0,0]]]

expected: 4

case 2

in: [[[0,1],[1,0]]]

expected: -1

case 3

in: [[[0]]]

expected: 0

case 4

in: [[[0,0],[0,0]]]

expected: 2

Starter codePython

def shortest_path_grid(grid):
    # Your code here
    pass

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