Warehouse Layout Optimization
Problem Statement
Amazon's fulfillment center has an N×M grid where each cell represents a shelf location. Some cells are blocked (obstacles), and some contain packages to be picked. Starting from the dispatch desk at (0,0), find the minimum number of steps to collect all packages and return to the dispatch desk. You can move up, down, left, or right, and cannot move through obstacles.
Company Use Case
Amazon warehouse robots use this exact path planning algorithm millions of times daily. The system must compute optimal pick-and-delivery routes across massive fulfillment centers while avoiding obstacles, other robots, and dynamically updating shelf locations. Amazon estimates this optimization saves over 40% in operational costs annually.
Examples
grid = [[0,2,0],[0,1,0],[0,2,0]]
8
Path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1)→(2,0)→(1,0)→(0,0). Pick packages at (0,1) and (2,1) on the way.
grid = [[0,2],[2,0]]
4
(0,0)→(0,1) pick→(1,1)→(1,0) pick→(0,0). Minimal route visiting both packages.
Constraints
- •2 ≤ N, M ≤ 100
- •Number of packages ≤ 10
- •0 = empty, 1 = obstacle, 2 = package
- •Starting cell (0,0) is always empty