Fastest Single-Mode Commute Across a Grid of Mode-Restricted Blocks
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
A city map is a grid of blocks. You must commute from your start block to your destination block using exactly one transport mode for the whole trip, and each mode may travel only on the blocks that allow it. Every mode has a fixed travel time and a fixed cost for each move between blocks. Return the name of the mode that gets you to the destination in the least total time.
The report names this problem without giving its input format; the format and tie rules below are fixed here so that every input has exactly one correct answer.
### Function Signature
```python
def fastest_commute_mode(grid: list[str], modes: list[str], time_per_block: list[int], cost_per_block: list[int]) -> str:
```
### Rules
- `grid[r][c]` is one of:
- `'S'`: the start block;
- `'D'`: the destination block;
- `'X'`: a blocked block that no mode can enter;
- a digit `'1'` to `'9'`: a block that only mode number `d` can enter, where mode number `d` is `modes[d - 1]`.
- A move goes from a block to one of its up to four neighbours (up, down, left, right) inside the grid. Diagonal moves are not allowed.
- With mode `i` (0-based), the trip starts on `'S'`, and each move may enter only a block marked with the digit `i + 1` or the `'D'` block. If `'S'` is next to `'D'`, every mode can make the trip in one move.
- A trip with mode `i` that makes `m` moves takes `m * time_per_block[i]` time and costs `m * cost_per_block[i]`.
- Each mode is judged by its trip with the fewest moves. A mode that cannot reach `'D'` at all is not a candidate.
- Return the name of the candidate with the smallest total time. Break ties by smaller total cost, then by smaller index in `modes`. Return the empty string `""` if no mode can reach `'D'`.
### Constraints
- `1 <= len(grid) <= 200` and `1 <= len(grid[r]) <= 200`; all rows have the same length.
- `grid` contains exactly one `'S'` and exactly one `'D'`; every other character is `'X'` or a digit from `'1'` to `str(len(modes))`.
- `1 <= len(modes) <= 9` and `len(time_per_block) == len(cost_per_block) == len(modes)`.
- Mode names are distinct, nonempty strings of English letters.
- `1 <= time_per_block[i] <= 10^4` and `0 <= cost_per_block[i] <= 10^4`.
- A shortest trip makes fewer than `40,000` moves, so every total time and total cost is below `4 * 10^8` and fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: grid = ["S11D",
"2XX2",
"2222"]
modes = ["Walk", "Bike"]
time_per_block = [10, 3]
cost_per_block = [0, 2]
Output: "Bike"
```
Walk reaches `D` along the top row in 3 moves: time 30, cost 0. Bike must go around the blocked blocks through the bottom row in 7 moves: time 21, cost 14. Bike is faster.
**Example 2**
```text
Input: grid = ["S22",
"1X2",
"11D"]
modes = ["Bus", "Taxi", "Train"]
time_per_block = [5, 5, 1]
cost_per_block = [2, 7, 1]
Output: "Bus"
```
Bus (down the left column, then along the bottom row) and Taxi (along the top row, then down the right column) both need 4 moves and take time 20. Bus costs 8 and Taxi 28, so Bus wins the tie. Train has no blocks of its own, cannot leave `S`, and is not a candidate even though it is the fastest per block.
**Example 3**
```text
Input: grid = ["SX",
"XD"]
modes = ["Walk"]
time_per_block = [1]
cost_per_block = [0]
Output: ""
```
Every neighbour of `S` is blocked, so no mode can reach `D`.
Overview: A grid coding problem: commute from a start block to a destination using one transport mode, where each mode may enter only its own blocks and has a per-block time and cost. Return the fastest mode, breaking ties by total cost and then list order, or an empty string when no mode can reach the destination.