Shortest Path on a 2D Grid | Dataford Interview Questions

An Amazon Robotics warehouse is represented as a rectangular grid. A cell with value 0 is traversable, and a cell with value 1 is blocked. Write a function that returns a shortest path from start to end, moving only up, down, left, or right.

Return the path as a list of [row, column] coordinates, including both endpoints. If no path exists, return an empty list. Any shortest path is acceptable.

Formal Specification

Input consists of a binary 2D list grid, a starting coordinate start, and a destination coordinate end. The function returns a list of coordinate lists. The start and destination cells are guaranteed to be traversable.

Constraints

1 <= rows, columns <= 200
grid is rectangular and contains only 0 and 1
start and end are valid traversable coordinates
Movement is allowed only up, down, left, and right
Any shortest path is accepted

Function Signature

def shortest_path(grid, start, end):

Your question is Shortest Path on a 2D Grid. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem