Search on Grids and Graphs | Dataford Interview Questions

A BrainOS robot represents a mapped floor area as a rectangular grid. Free cells are marked 0, and blocked cells such as walls or unavailable areas are marked 1. Given a start cell and a goal cell, return the shortest route the robot can follow using four-directional movement.

If multiple shortest routes exist, explore neighbors in this order: up, right, down, left. Return the first route produced by that ordering. If the goal cannot be reached, return an empty list.

Formal Specification

Implement navigate_grid(grid, start, goal).

grid is a non-empty rectangular list of lists containing integers 0 or 1.
start and goal are two-element lists [row, column] identifying free cells.
The robot may move to an adjacent cell vertically or horizontally, but not diagonally or through blocked cells.
Return a list of coordinate lists beginning with start and ending with goal, or [] when no route exists.

Constraints

1 <= rows, columns <= 200
grid is rectangular and contains only 0 and 1
start and goal are coordinates of free cells
Movement is limited to four cardinal directions
The returned route must include both endpoints when one exists

Function Signature

def navigate_grid(grid, start, goal):

Your question is Search on Grids and Graphs. 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