Grid Shortest Path

Problem

Given a grid of 0 open cells and 1 walls, return the minimum number of steps from start to end moving up, down, left or right, or -1 if no path exists.

Run breadth-first search from start, recording the distance when a cell is first reached. Return -1 if start or end is a wall, and 0 when start equals end.

Hint

BFS explores cells in order of increasing distance, so the first time you reach the end is optimal.

Test cases

case 1

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

expected: 4

case 2

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

expected: -1

case 3

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

expected: 0

case 4

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

expected: -1

case 5

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

expected: 2

Starter codePython

def shortest_path_grid(grid, start, end):
    # Your code here
    pass

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