Shortest Path in a Grid

Difficulty: Medium · Topic: Pathfinding

Given a grid of 0 (open) and 1 (blocked), return the length of the shortest path from the top-left (0,0) to the bottom-right corner, moving 4-directionally through open cells. Length counts the cells visited (start and end included). Return -1 if there is no path. BFS explores by distance, so the first time it reaches the goal is the shortest path.

Examples

shortest_grid_path([[0,0,1],[1,0,0],[1,1,0]])
→ 5

Down the open diagonal: 5 cells.

shortest_grid_path([[0,1],[1,0]])
→ -1

Diagonal moves aren't allowed.

Target complexity: time O(R·C), space O(R·C)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.