Find a Lexicographically Optimal Robot Path with Charging Cells

Problem Statement

You are given an R x C grid where each cell is either empty (0), an obstacle (1), or an automatic charging station (2). A robot needs to navigate from start = (sr, sc) to target = (tr, tc) by moving horizontally or vertically to adjacent non-obstacle cells.

Moving between adjacent cells consumes 1 unit of battery power. Whenever the robot enters a cell with a charging station (2), its battery is instantly recharged to full capacity.

Among all valid paths from start to target, find the path that is optimal according to the following criteria, compared strictly in lexicographical order:

1. Minimize the number of charging stations entered: Count how many times the robot steps into a cell with value 2 (excluding start if start itself is a charging station).
2. Minimize the required battery capacity: Defined as the maximum number of steps taken in any single segment without charging (i.e., from start to the first charge, between consecutive charges, or from the last charge to target).
3. Minimize total moves: Total number of steps taken (path length minus 1).
4. Tie-break lexicographically: If multiple paths match on all three metrics, choose the path whose sequence of flattened cell indices (r * C + c) is lexicographically smallest.

Return the optimal path as a list of flattened cell indices from start to target. If no path exists, return an empty list [].

Function Signature

def find_optimal_path(grid: list[list[int]], start: tuple[int, int], target: tuple[int, int]) -> list[int]:
    pass

Constraints

• 1 <= R, C <= 20
• 0 <= number of charging stations <= 10
• grid[r][c] in {0, 1, 2}
• Neither start nor target is an obstacle (grid[r][c] != 1).

Examples

Example 1

Input:
grid = [
  [0, 0, 0],
  [1, 2, 1],
  [0, 0, 0]
]
start = (0, 0)
target = (2, 2)

Output: [0, 1, 2, 5, 8]
Explanation:
- Path 1: (0,0) -> (0,1) -> (0,2) -> (1,2 is obstacle, so around) -> ...
  Empty path along the border uses 0 charging stations, length 6 (e.g. indices 0 -> 1 -> 2 -> ... wait, (1,2) is blocked). So path goes: (0,0) -> (0,1) -> (0,2) is dead-end because (1,2) is blocked. Path around: (0,0) -> (0,1) -> charging station at (1,1)? But (1,0) is blocked.
  Let's trace: (0,0)->(0,1)->(0,2) has no down step. Wait, indices:
  (0,0)=0, (0,1)=1, (0,2)=2, (1,0)=3(blocked), (1,1)=4(station), (1,2)=5(blocked), (2,0)=6, (2,1)=7, (2,2)=8.
  Path: (0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2) uses 1 charging station.
  Flattened indices: [0, 1, 4, 7, 8].

Example 2

Input:
grid = [
  [0, 0],
  [0, 0]
]
start = (0, 0)
target = (1, 1)

Output: [0, 1, 3]
Explanation:
There are two shortest paths of length 2:
- (0,0) -> (0,1) -> (1,1) has indices [0, 1, 3]
- (0,0) -> (1,0) -> (1,1) has indices [0, 2, 3]
Both use 0 charging stations, max capacity 2, and 2 moves. [0, 1, 3] is lexicographically smaller than [0, 2, 3].