Feature #12: Warehouse and Drop Points

Implement the "Warehouse and Drop Points" feature for our "Amazon" project.

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 2311=21474836472^{31} - 1 = 2147483647 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 nearest drop point, so that the robots can use these precomputed distances to decide on the shortest routes.

Let us look at an example to better understand this:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.