Fastest single-mode commute on a city grid

You are planning a commute across a city drawn as a 2D grid of characters:

• 'S': your starting point (exactly one).
• 'D': your destination (exactly one).
• '1' to 'k': a block that only transport mode i can use.
• 'X': a blocked cell.

You are also given two arrays of length k. time[i-1] and cost[i-1] are the minutes and dollars that mode i spends per block.

You pick one mode for the whole trip and cannot switch. Moves go up, down, left or right. A trip in mode i may step only on S, D and cells labelled i. Its total time is (blocks travelled) × time[i-1], and its total cost is (blocks travelled) × cost[i-1]. S and D do not count as blocks.

Implement optimal_commute(grid: list[str], time: list[int], cost: list[int]) -> int. It returns the mode number with the smallest total time. Break ties by smaller total cost, then by smaller mode number. Return -1 if no single mode can reach D.

Constraints: 1 <= rows, cols <= 500, 1 <= k <= 9, 1 <= time[i], cost[i] <= 1000.

Example 1

grid = ["S2D",
        "1X1",
        "111"]
time = [1, 9], cost = [9, 1]

Mode 1 goes around the wall through 5 blocks, for time 5. Mode 2 uses 1 block, for time 9. Answer: 1.

Example 2

Same grid, time = [9, 2], cost = [1, 1]. Mode 1 takes 45 and mode 2 takes 2. Answer: 2.

Example 3

grid = ["S12D"]. Reaching D needs both modes, and switching is not allowed. Answer: -1.