BFS for Robot Pathing Grid | Dataford Interview Questions

Foundation Robotics Labs represents a robot's navigation area as a rectangular grid. Write a function that returns the breadth-first search traversal order of every open cell reachable from a given start position.

Cells containing . are traversable, and cells containing # are blocked. The robot may move one cell up, right, down, or left, but not diagonally. Visit neighbors in that order whenever multiple choices are available. Return coordinates as [row, column] pairs.

Formal Specification

Implement bfs_robot_grid(grid, start), where grid is a non-empty list of equal-length strings and start is a two-element list [row, column]. Return a list of coordinate pairs representing the BFS order of reachable open cells. The start cell must be open. If a cell can be reached by multiple routes, include it only once, when it is first discovered.

Constraints

1 <= rows, columns <= 500
grid contains equal-length strings
Each cell is either '.' or '#'
start identifies an open cell
Movement is limited to up, right, down, and left

Function Signature

def bfs_robot_grid(grid, start):

Your question is BFS for Robot Pathing 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 <= rows, columns <= 500
grid contains equal-length strings
Each cell is either '.' or '#'
start identifies an open cell
Movement is limited to up, right, down, and left

Function Signature

def bfs_robot_grid(grid, start):

Your question is BFS for Robot Pathing 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.