Fastest Single-Mode Commute on a Grid with Per-Step Time and Cost

A city map is given as a rectangular grid of characters. Exactly one cell is `'S'` (your start) and exactly one cell is `'D'` (your destination). Every other cell is one of the digits `'1'`, `'2'`, `'3'`, `'4'`, meaning the cell is a path usable only by that commute mode, or `'X'`, meaning no mode can enter it. For each of the four commute modes you are given the time one step takes and the cost of one step. A commute uses a single mode for the whole trip. Determine which mode gets you from `'S'` to `'D'` in the least total time. If several modes tie on time, pick the one with the least total cost. ### Function Signature ```python def fastest_commute_mode(grid: list[str], time: list[int], cost: list[int]) -> int: ``` ### Rules - A step moves from the current cell to one of its four edge-adjacent neighbors (up, down, left, right). Diagonal moves are not allowed. - When traveling with mode `m` (1 to 4), a step may enter a cell only if the cell is labeled with the digit `m` or is the destination `'D'`. The trip starts on `'S'`. Cells labeled `'X'`, cells of other modes, and `'S'` itself cannot be entered. - Every step taken with mode `m` adds `time[m - 1]` to the total time and `cost[m - 1]` to the total cost, so a trip of `s` steps with mode `m` takes `s * time[m - 1]` time and `s * cost[m - 1]` cost. Each mode's trip uses the fewest steps possible for that mode. - Return the mode number (1 to 4) with the smallest total time. Break ties by smaller total cost, then by smaller mode number. - Return `-1` if no mode can reach `'D'`. - The original report does not describe cells that are neither `'S'`, `'D'` nor a digit; this version uses `'X'` for blocked cells. ### Constraints - `1 <= len(grid) <= 500` and `1 <= len(grid[r]) <= 500`; all rows have the same length. - Every character is one of `'S'`, `'D'`, `'X'`, `'1'`, `'2'`, `'3'`, `'4'`, and exactly one `'S'` and exactly one `'D'` appear. - `len(time) == len(cost) == 4`, and `1 <= time[i], cost[i] <= 10^4`. - A total time or total cost can reach about `2.5 * 10^9`, which exceeds `2^31 - 1`; use 64-bit arithmetic in fixed-width languages. - These numeric limits are practice bounds; the original report did not state input sizes. ### Examples **Example 1** ```text grid = ["S11X", "2X1X", "2X11", "222D"] time = [3, 2, 1, 1] cost = [1, 5, 1, 1] Output: 2 ``` Mode 1 needs 6 steps (right, right, down, down, right, down): time 18, cost 6. Mode 2 needs 6 steps (down, down, down, right, right, right): time 12, cost 30. Modes 3 and 4 cannot leave `'S'`. Mode 2 is the fastest. **Example 2** ```text grid = ["S11X", "2X1X", "2X11", "222D"] time = [2, 2, 5, 5] cost = [1, 3, 1, 1] Output: 1 ``` Modes 1 and 2 both take 12 time units. Mode 1 costs 6 and mode 2 costs 18, so mode 1 wins the tie. **Example 3** ```text grid = ["S1X", "XXD"] time = [1, 1, 1, 1] cost = [1, 1, 1, 1] Output: -1 ``` Mode 1 can step to the cell right of `'S'` but is walled in there. No mode reaches `'D'`.