Uber Senior Software Engineer Interview Experience — A Three-Level Robot Path Optimization

In a grid, a robot needs to move from a starting point to a destination. Each move consumes one unit of battery power. Charging cells are distributed throughout the grid, and when the robot reaches one, its battery is recharged to full. The task is to find an optimal path using the following priorities, compared lexicographically:

1. Minimize the number of charging cells used.
2. Minimize the maximum battery capacity the robot requires.
3. Minimize the total number of moves.

Key ideas and points to watch:

1. State: A state needs to be represented as (row, col, currentBattery). Because the robot can visit the same cell multiple times with different amounts of battery remaining, the visited set must record both the coordinates and the battery level at that time, rather than recording only the position.
2. Algorithm: Use a modified Dijkstra algorithm with a priority queue. The queue must be ordered strictly by (chargingCells, maxBattery, moves), following the priority order above.