Return a Shortest Path Through a Binary Grid
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement `shortest_grid_path(grid)` for a square binary matrix. A cell containing `0` is open and a cell containing `1` is blocked. Start at the top-left cell and reach the bottom-right cell through open cells. Each step may move horizontally, vertically, or diagonally to any of the eight neighboring cells.
Return one shortest path as `[[row, column], ...]`, including both endpoints. Return an empty list if either endpoint is blocked or no path exists.
For deterministic output, explore neighbor offsets in this order: `[-1,-1]`, `[-1,0]`, `[-1,1]`, `[0,-1]`, `[0,1]`, `[1,-1]`, `[1,0]`, `[1,1]`. Among shortest paths, return the one discovered by breadth-first search with that order.
```hint Record how each cell was reached
Store one parent coordinate when a cell is first discovered. This avoids copying an entire partial path into every queue entry.
```
```hint Reconstruct backward
Once the destination is reached, follow parent links to the start and reverse the collected coordinates.
```
Quick Answer: Return one deterministic shortest path through an eight-directional binary grid using breadth-first search. Learn parent tracking, ordered neighbor exploration, blocked-endpoint handling, and efficient path reconstruction.
Implement shortest_grid_path(grid) for a square binary matrix, moving through open zero cells in any of eight directions. Return one shortest endpoint-inclusive path, or an empty list when blocked or unreachable; break shortest-path ties by breadth-first discovery using offsets [-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1].
Constraints
- 0 <= grid.length <= 20, and every nonempty grid is square.
- Every cell is 0 for open or 1 for blocked.
- The returned path must use the specified neighbor order to make shortest-path ties deterministic.
Examples
Input: ([[0, 0, 0], [1, 1, 0], [0, 0, 0]],)
Expected Output: [[0, 0], [0, 1], [1, 2], [2, 2]]
Input: ([[0, 1], [1, 0]],)
Expected Output: [[0, 0], [1, 1]]
Hints
- Breadth-first search discovers cells in nondecreasing path length; record a parent only on first discovery.
- Reconstruct from the destination through parent coordinates, then reverse the collected path.