Robot Warehouse Navigation - Grid Coding Interview

Question

## Problem

A warehouse is a 2D grid. A robot starts at position `S` and must collect all packages marked `P`, then return to `S`. The robot moves one cell at a time (4-directional). Walls are `#`. Find the minimum total steps to collect all packages and return to start.

```python
def min_steps_collect_all(grid: list[str]) -> int:
    # Return -1 if any package is unreachable
    ...
```

**Example:**
```
grid = [
  "S.P",
  "...",
  "P.#"
]
Output: 10  # BFS distances: S->(0,2) cost 2, (0,2)->(2,0) cost 4, (2,0)->S cost 4. Total=10.
            # Or other orderings -- pick the minimum.
```

**Constraint:** At most 4 packages on the grid.

## Approach

Pre-compute BFS shortest paths between all pairs of key locations (S and each P). Then use bitmask DP over `(current_pos, collected_set)` to find minimum tour.

## Follow-ups
- Why is bitmask DP tractable here for at most 4 packages?
- How does the problem change if the robot can carry at most 1 package at a time (must return to S between pickups)?
- Extend to multiple robots: minimize makespan (last robot to finish).

Robot Warehouse Navigation - Grid Coding Interview

Question Details

Full Details

Topics

More from Codesignal