Robot Path in Grid with Charging Stations (Multi-Priority Optimization)

Problem Statement

Given a grid with a starting cell, a destination cell, normal cells, and charging cells, find the optimal path for a robot to reach the destination.

• Each move consumes 1 unit of battery
• Visiting a charging cell recharges the battery to full
• The robot starts with a full battery of capacity C

Optimize the path in this priority order:

1. Minimum charging cells used
2. Minimum battery required (max battery needed at any point)
3. Minimum total moves

Constraints

• 1 <= grid dimensions <= 100 x 100
• Battery capacity 1 <= C <= 1000
• Grid cells: start S, destination D, normal ., charging *, obstacle #
• Robot moves in 4 directions

Example

S . . *
# # . #
. . . D

Battery capacity = 3

The robot must navigate around obstacles, possibly detour to the charging cell *, and reach D while minimizing charging cells used first, then battery, then moves.

What the Interviewer Expects

1. Recognize it's a state-space search — state = (row, col, currentBattery). Not a simple shortest path.
2. Multi-criteria optimization — use a priority queue ordered by the lexicographic priority: (chargingCellsUsed, maxBatteryNeeded, moves).
3. Modified Dijkstra — the "cost" is a tuple, compared in priority order.
4. State tracking — you can revisit a cell with a different battery level, so visited must account for battery state.
5. Dry run — walk through a small example showing the priority queue evolution.

Follow-ups

1. What if charging cells have a cost (money) to use? How does the optimization change?
2. What if the robot can carry a limited number of spare batteries?
3. What if some cells drain 2 battery instead of 1 (terrain difficulty)?
4. How would you handle a grid too large to fit in memory?