Shortest Path in 3D Grid | Dataford Interview Questions

A robot operating in a GM Factory ZERO workcell must move through a 3D grid containing traversable cells and blocked cells. Implement shortest_path_3d to return the least-cost path between two coordinates.

Formal Specification

The grid is represented as grid[z][y][x]. Each cell contains -1 for an obstacle or a nonnegative traversal cost for a free cell. Moving to an adjacent free cell costs the value of the destination cell. The starting cell's cost is not included. The robot may move in six directions: positive or negative x, y, or z.

Return the path as a list of coordinates in [z, y, x] format, including both start and end. Return [] if the destination is unreachable. The start and end coordinates are guaranteed to be in bounds and free.

Constraints

1 <= depth, height, width <= 100
The grid is rectangular and contains at most 10^6 cells
Each free-cell cost is an integer from 0 through 9
Blocked cells are represented by -1
Movement is limited to six axis-aligned directions
The start and end cells are in bounds and free

Function Signature

def shortest_path_3d(grid, start, end):

Your question is Shortest Path in 3D 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

Formal Specification

Constraints

1 <= depth, height, width <= 100
The grid is rectangular and contains at most 10^6 cells
Each free-cell cost is an integer from 0 through 9
Blocked cells are represented by -1
Movement is limited to six axis-aligned directions
The start and end cells are in bounds and free

Function Signature

def shortest_path_3d(grid, start, end):

Your question is Shortest Path in 3D 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.