Feature #12: Warehouse and Drop Points
Understand how to model an Amazon warehouse as a 2D grid and precompute shortest distances from open spaces to the nearest drop points using breadth-first search. Learn techniques to optimize robot navigation by calculating minimal paths efficiently in a grid representing shelves, corridors, and drop points.
We'll cover the following...
Description
We have mapped an Amazon warehouse into a rectangular grid. There are several shelves on the floor. Furthermore, there are drop points that connect the warehouse to the delivery vans. We have robots that are programmed to fetch items from the shelves and drop them off at the nearest drop point.
The warehouse is represented as a 2D array. A cell with -1 represents a shelf, a cell with 0 represents a drop point, and the infinite value represents an open space (corridor) that the robot can tread to move from shelves to the nearest drop points.
Robots need to navigate the warehouse to pick up items, one at a time, and drop them off at the nearest drop points. The distances from every open space to the nearest drop point need to be pre-computed for efficiency.
An open space in a warehouse is represented by an infinite value. In this case, we will consider an infinite value. The distance from any open space to the nearest drop point will not exceed this value.
Our task is to precompute the distance between every cell and its ...