Databricks 面试真题解析：二维网格最短通勤方式选择

You live in San Francisco city and want to minimize your commute time to the Databricks HQ.

Given a 2D matrix of the San Francisco grid and the time as well as cost matrix of all the available transportation modes, return the fastest mode of transportation. If there are multiple such modes, then return the one with the least cost.

Sample Input:

2D Grid:
|3|3|S|2|X|X|
|3|1|1|2|X|2|
|3|1|1|2|2|2|
|3|1|1|1|D|3|
|3|3|3|3|3|4|
|4|4|4|4|4|4|

Legend:
X = Roadblock
S = Source
D = Destination
1 = Walk, 2 = Bike, 3 = Car, 4 = Train

Transportation Modes: ["Walk", "Bike", "Car", "Train"]
Cost Matrix (Dollars/Block): [0, 1, 3, 2]
Time Matrix (Minutes/Block): [3, 2, 1, 1]

Note: In this example, we are only counting the blocks between 'S' and 'D' to compute the minimum time and dollar cost.

Sample Output: Bike

这道题本质上是一个“按网格路径统计代价”的选择题：先根据二维矩阵找到源点 S 和终点 D 之间可走的路径，再结合不同交通方式在每个 block 上的耗时和费用，计算哪种方式总时间最短；如果最短时间相同，则选择总费用更低的方式。解题时通常需要先遍历网格，处理障碍 X，并统计 S 到 D 之间的有效步数；然后把步数分别乘上各交通方式的 time/cost，按“先时间、后费用”的规则比较即可。样例中 Bike 的总时间更优，因此输出 Bike。