Coding questions · Disney

Solve grid shortest path with BFS

This question evaluates understanding of grid traversal and shortest-path graph search, including modeling a 2D grid with obstacles and reasoning about boundary and edge cases, within the Coding & Algorithms domain.

Given a 2D grid containing 0s (open cells) and 1s (walls), and coordinates for a start (sr, sc) and a target (tr, tc), return the length of the shortest path from start to target using 4-directional moves (up, down, left, right). If no path exists, return -1. Specify the algorithm, analyze time and space complexity, and discuss edge cases such as starting equals target, boundaries, and large grids.

Grid Shortest Path with BFS

Return the length of the shortest four-directional path from start to target in a 0/1 grid, or -1 if unreachable.

Examples

Example 1

Input: ([[0,0,0],[1,1,0],[0,0,0]], (0,0), (2,2))
Output: 4

Explanation: Path around walls.

Example 2

Input: ([[0,1],[1,0]], (0,0), (1,1))
Output: -1

Explanation: Blocked target.

Hints

Choose a representation that makes the core operation simple.
Handle empty and boundary inputs before the main algorithm.