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.

Charge-Aware Robot Route: Fewest Charges, Smallest Battery, Fewest Moves

Hints

1. 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.
2. 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.
3. Two partial routes reaching the same place can be incomparable: one may have a shorter longest run while the other has used fewer moves.

Approach

Charges first. Let level(x) be the fewest charging moves on any walk from S that reaches x without passing through D. A layered 0-1 BFS computes it: entering a C cell costs 1, entering S, '.' or D costs 0, and D is never expanded because the journey ends there. If level(D) is infinite the answer is [-1, -1, -1]; otherwise charges = k = level(D). Battery size never affects reachability, so this is the true minimum.

Structure of minimum-charge routes. If a minimum-charge route visited some cell x with more than level(x) charges, replacing its prefix up to x with a cheaper walk would lower the total, which is a contradiction. So every cell on such a route is visited with exactly level(x) charges. The route therefore splits into k + 1 stretches: stretch i starts at S (i = 0) or at a charger of level i, passes only through non-charging cells of level i, and ends with a move onto a charger of level i + 1 (or onto D when i = k). No charger is ever entered twice on such a route. The route's capacity is its longest stretch, because a stretch of L moves needs B >= L and arriving with 0 units is allowed. Its moves value is the sum of the stretches. For a fixed pair of endpoints, only the shortest stretch matters, because it is never worse for either quantity.

Algorithm. For each level-i endpoint, a BFS confined to non-charging cells of level i yields weighted edges to the level-(i + 1) chargers (or to D) that it can reach. This builds a layered DAG. Processing layers in order, a min-max DP gives capacity = min over DAG paths of the largest edge. A second pass over the same edges, keeping only edges no longer than that capacity, gives the shortest total length, which is moves. The two quantities cannot be merged into one greedy label per node. A partial route with a smaller longest stretch can have more moves, and a later long stretch can erase its capacity advantage (see the test with answer [2, 5, 11]).

Edge cases: S walled in or separated from D by walls; D adjacent to S; adjacent chargers, which form a stretch of length 1 and each count as a charge; dead-end chargers, which are never worth entering because they add a charge; and grids whose route needs no charger, where capacity equals moves.

• Time complexity: O(RC(K+1)), where R*C is the grid size and K is the number of charging cells (one confined BFS per stretch start)
• Space complexity: O(R*C + (K+1)^2) for the grid arrays and the stored stretch edges