Fastest Single-Mode Commute on a Grid with Per-Step Time and Cost
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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'`.
Overview: Given a city grid with a start, a destination and cells usable by only one of four commute modes, choose the mode whose trip takes the least total time, breaking ties by lower total cost. Tests shortest-path search on grids, per-mode reachability and precise tie-breaking.
A city map is given as a rectangular grid of characters `grid`, a list of equal-length strings with one string per row. 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: mode `m` (1 to 4) uses `time[m - 1]` per step and `cost[m - 1]` per step. A commute uses a single mode for the whole trip.
### 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`, the trip starts on `'S'`, and a step may enter a cell only if the cell is labeled with the digit `m` or is the destination `'D'`. Cells labeled `'X'`, cells of other modes, and `'S'` itself cannot be entered.
- Each mode's trip uses the fewest steps possible for that mode. A trip of `s` steps with mode `m` takes total time `s * time[m - 1]` and total cost `s * cost[m - 1]`.
- Among the modes that can reach `'D'`, 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'`.
Total time and total cost are bounded by about `2.5 * 10^9`, which exceeds `2^31 - 1`, so compute them with 64-bit integers (`long` in Java, `long long` in C++). The returned mode number always fits in an `int`.
Implement `fastest_commute_mode(grid, time, cost)`.
### 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.
### 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 is bounded by about `2.5 * 10^9`, which exceeds `2^31 - 1`; use 64-bit arithmetic in fixed-width languages.
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 is bounded by about 2.5 * 10^9, which exceeds 2^31 - 1; use 64-bit arithmetic in fixed-width languages (long in Java, long long in C++).
Examples
Input: (['S11X', '2X1X', '2X11', '222D'], [3, 2, 1, 1], [1, 5, 1, 1])
Expected Output: 2
Explanation: Source Example 1: modes 1 and 2 each need 6 steps; mode 2 totals time 12 against mode 1's 18.
Input: (['S11X', '2X1X', '2X11', '222D'], [2, 2, 5, 5], [1, 3, 1, 1])
Expected Output: 1
Explanation: Source Example 2: modes 1 and 2 tie at total time 12; mode 1 has the lower total cost, 6 against 18.
Hints
- Modes never mix within a trip, so treat each of the four modes on its own: which cells may that mode enter, and what is the fewest number of steps from 'S' to 'D' through them?
- Within one mode every step adds the same time and the same cost, so a mode's totals follow directly from its step count.
- Only modes that actually reach 'D' compete. Compare total time first, then total cost (not per-step cost), then mode number; if none reaches 'D', the answer is -1.