Robot Grid Route with Charging Cells: Fewest Charges, Then Battery, Then Moves
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A robot must travel across a 2D grid from a starting cell to a destination cell. Each cell of the grid is one of these characters:
- `S`: the starting cell
- `D`: the destination cell
- `.`: a normal traversable cell
- `C`: a charging cell
- `#`: a blocked cell that the robot cannot enter
The robot moves up, down, left or right to an adjacent cell that is not blocked, and each move consumes 1 unit of battery. Whenever the robot enters a charging cell, its battery is immediately restored to its maximum capacity.
Find the optimal route from `S` to `D` under these priorities, compared in lexicographic order:
1. Minimize the number of charging cells visited.
2. Among routes that visit the minimum number of charging cells, minimize the initial battery capacity required to complete the journey.
3. If several routes still tie, minimize the total number of moves.
Return the optimal route's three values as `[charges, capacity, moves]`, or `[-1, -1, -1]` if `D` cannot be reached.
### Function Signature
```python
def best_route(grid: list[str]) -> list[int]:
```
### Rules
- The battery capacity is a non-negative integer `B` fixed before the journey. The robot starts on `S` with a full battery of `B` units, and a charging cell restores the battery to `B`.
- A move needs at least 1 unit of battery and uses exactly 1 unit, so the battery never goes negative. The battery becomes `B` right after a move that ends on a `C` cell. Moves onto `S`, `.` or `D` do not charge.
- The robot may enter `S`, `.`, `C` and `D` cells. It never enters `#` and never leaves the grid. A route may revisit cells.
- The journey ends the first time the robot enters `D`. Arriving there with 0 units left is allowed.
- For a route, `charges` is the number of its moves that end on a `C` cell (entering the same charging cell twice counts twice), `capacity` is the smallest `B` with which the robot can complete it, and `moves` is its number of moves.
- Return the lexicographically smallest `[charges, capacity, moves]` over all routes from `S` to `D`. Only these values are returned, so the answer is unique even when several routes achieve them.
### Constraints
- `1 <= len(grid) <= 50` and `1 <= len(grid[i]) <= 50`, and all rows have the same length.
- Every character is one of `S`, `D`, `.`, `C` and `#`.
- The grid contains exactly one `S` and exactly one `D`.
- Every value in the answer fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: grid = [
"S.C.D",
".###.",
"....."
]
Output: [0, 8, 8]
```
Going right along the top row reaches `D` in 4 moves with capacity 2, but it enters the charging cell at `(0, 2)`. The route down the left column, along the bottom row and up the right column avoids every charging cell, so it wins on the first priority even though it needs 8 moves and a capacity of 8.
**Example 2**
```text
Input: grid = [
"SC...",
".#...",
".#..D",
".C..."
]
Output: [1, 4, 8]
```
Column `1` holds only charging and blocked cells, so every route enters at least one charging cell. Through the charger at `(0, 1)`, the robot needs 1 move to reach it and then at least 5 more to reach `D`: capacity 5 and 6 moves. Through the charger at `(3, 1)`, it needs 4 moves to reach it and 4 more to reach `D`: capacity 4 and 8 moves. Capacity outranks moves, so the second route is optimal.
**Example 3**
```text
Input: grid = [
"S#.",
"##D"
]
Output: [-1, -1, -1]
```
Both neighbors of `S` are blocked, so `D` is unreachable.
Overview: A grid pathfinding problem in which a robot travels from a start cell to a destination through open, blocked and charging cells, spending one battery unit per move and refilling at chargers. The best route is ranked by fewest charging stops, then smallest required battery capacity, then fewest moves.
A robot travels across a 2D grid from a starting cell to a destination cell. Each cell of `grid` is one of these characters:
- `S`: the starting cell
- `D`: the destination cell
- `.`: a normal traversable cell
- `C`: a charging cell
- `#`: a blocked cell that the robot cannot enter
The robot moves up, down, left or right to an adjacent cell that is not blocked, and each move consumes 1 unit of battery. Whenever the robot enters a charging cell, its battery is immediately restored to its maximum capacity.
Find the optimal route from `S` to `D` under these priorities, compared in lexicographic order:
1. Minimize the number of charging cells visited.
2. Among routes that visit the minimum number of charging cells, minimize the initial battery capacity required to complete the journey.
3. If several routes still tie, minimize the total number of moves.
Implement `best_route(grid)`, which returns the optimal route's three values as `[charges, capacity, moves]`, or `[-1, -1, -1]` if `D` cannot be reached.
### Rules
- The battery capacity is a non-negative integer `B` fixed before the journey. The robot starts on `S` with a full battery of `B` units, and a charging cell restores the battery to `B`.
- A move needs at least 1 unit of battery and uses exactly 1 unit, so the battery never goes negative. The battery becomes `B` right after a move that ends on a `C` cell. Moves onto `S`, `.` or `D` do not charge.
- The robot may enter `S`, `.`, `C` and `D` cells. It never enters `#` and never leaves the grid. A route may revisit cells.
- The journey ends the first time the robot enters `D`. Arriving there with 0 units left is allowed.
- For a route, `charges` is the number of its moves that end on a `C` cell (entering the same charging cell twice counts twice), `capacity` is the smallest `B` with which the robot can complete it, and `moves` is its number of moves.
- Return the lexicographically smallest `[charges, capacity, moves]` over all routes from `S` to `D`. Only these values are returned, so the answer is unique even when several routes achieve them.
### Constraints
- `1 <= len(grid) <= 50` and `1 <= len(grid[i]) <= 50`, and all rows have the same length.
- Every character is one of `S`, `D`, `.`, `C` and `#`.
- The grid contains exactly one `S` and exactly one `D`.
- Every value in the answer fits in a 32-bit signed integer (it never exceeds 2^31 - 1), so `int` is sufficient in Java and C++.
### Example 1
```text
Input: grid = ["S.C.D", ".###.", "....."]
Output: [0, 8, 8]
```
Going right along the top row reaches `D` in 4 moves with capacity 2, but it enters the charging cell at `(0, 2)`. The route down the left column, along the bottom row and up the right column avoids every charging cell, so it wins on the first priority even though it needs 8 moves and a capacity of 8.
### Example 2
```text
Input: grid = ["SC...", ".#...", ".#..D", ".C..."]
Output: [1, 4, 8]
```
Column `1` holds only charging and blocked cells, so every route enters at least one charging cell. Through the charger at `(0, 1)`, the robot needs 1 move to reach it and then at least 5 more to reach `D`: capacity 5 and 6 moves. Through the charger at `(3, 1)`, it needs 4 moves to reach it and 4 more to reach `D`: capacity 4 and 8 moves. Capacity outranks moves, so the second route is optimal.
Constraints
- 1 <= len(grid) <= 50 and 1 <= len(grid[i]) <= 50, and all rows have the same length.
- Every character is one of S, D, ., C and #.
- The grid contains exactly one S and exactly one D.
- Every value in the answer fits in a 32-bit signed integer (it never exceeds 2^31 - 1), so int is sufficient in Java and C++.
Examples
Input: (['SD'],)
Expected Output: [0, 1, 1]
Explanation: Smallest row: D is adjacent to S, one move needing capacity 1.
Input: (['S', 'D'],)
Expected Output: [0, 1, 1]
Explanation: Smallest column: one move down onto D.
Hints
- Battery size never changes which cells the robot can reach, so first ask how few charging cells any route from S to D must enter.
- A route's required capacity is the length of its longest run of moves without a charge, including the run from S to the first charge and the run from the last charge to D.
- Two partial routes reaching the same place can be incomparable: one may have a shorter longest run while the other has used fewer moves.