Graph Traversal Implementation

EasyPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Graph Traversal Implementation. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

A mobile robot must move through a simplified floor layout containing Supermicro SuperServer rack positions and open aisles. Given a rectangular grid, find the minimum number of moves from a start cell to a goal cell.

A cell containing 0 is traversable, while a cell containing 1 is blocked. In one move, the robot may travel one cell up, down, left, or right. Return the minimum number of moves, or -1 if the goal cannot be reached.

Formal Specification

Implement shortest_path(grid, start, goal), where grid is a list of equal-length lists containing 0 or 1, and start and goal are two-element [row, column] coordinates. Return an integer.

Constraints

1 <= rows, columns <= 500
Every row has the same number of columns
Each grid value is either 0 or 1
start and goal are valid coordinates on traversable cells
Movement is allowed only up, down, left, and right

Function Signature

def shortest_path(grid, start, goal):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output