题目背景

面试中给定一个二维网格，每个格子代表：

• 交通方式编号（不同的交通方式如步行、公交、地铁等）

• 障碍物（表示为 block）

• 起点 S 和终点 D

要求是选择一种交通方式，只能在该方式的格子内进行四向移动，最终到达终点 D。需要返回最短时间能到达的交通方式。如果多个交通方式的时间相同，则比较其总成本。

思路

1. 枚举交通方式：从起点 S 开始，使用 BFS（广度优先搜索）进行搜索，因为 BFS 可以保证在没有障碍物的情况下找到最短路径。

2. 搜索每种交通方式的路径：每种交通方式有对应的网格（只包含该交通方式的格子），使用 BFS 寻找从 S 到 D 的路径并记录时间。

3. 比较时间与成本：每找到一种可能的路径，就更新最短路径和最低成本，最终返回最优的交通方式。

Follow-up 问题

1. 优化算法：问是否能优化上述方法，避免枚举所有交通方式。可以考虑多源 BFS，即一次性从所有交通方式的起点同时进行搜索，记录每种交通方式到终点的最短路径，减少不必要的计算。

2. 返回具体路径：面试官要求输出从 S 到 D 的路径。在 BFS 中，除了记录每个点是否访问过，还要记录前驱节点，这样当找到终点时，可以通过回溯前驱节点构建路径。