Robot Grid Route with Charging Cells: Fewest Charges, Then Battery, Then Moves

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

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

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

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

Input: grid = [
 "S#.",
 "##D"
]
Output: [-1, -1, -1]

Both neighbors of S are blocked, so D is unreachable.