We have Uber HCV (High Capacity Vehicles) plying on the same routes in loops. Every route has a certain number of stops. The routes are represented as a 2D array, where each route[i] shows the route that the i-th HCV takes. For example, the 1st HCV route would be 1 -> 2 -> 7 -> 1 -> 2 -> 7 ... and so on. Find the minimum number of HCV transfers needed given a source and a destination stop.
Example 1:
Input: HCV routes: [[1, 2, 7], [3, 6, 7]], Source: 1, Destination: 7
Output: 0
(get into the first HCV on stop 1 and get down at stop 7, no hops needed)Source: 1, Destination: 6
Output: 1
(get into the first HCV on stop 1, transfer on stop 7 to the next HCV and then get down at stop 6 from the other HCV, hence it needed 1 hop)Return -1 if it’s unable to reach the destination from the given source.
Example 2:
HCV routes: [[1,2,3,4,5,6,7,8,9,10], [2,7]]
Source: 1, Destination: 7
Output: 0这道题本质上是一个“公交线路最少换乘”问题。每条 HCV 路线可以看作一条循环线路，题目要求从 source 到 destination 的最少换乘次数；如果 source 和 destination 本来就在同一条线路上，答案就是 0，否则需要在共享站点处换乘。常见做法是先建立“站点 -> 线路”的映射，再从 source 所在的所有线路出发做 BFS，把“线路”作为图中的节点、两个线路共享站点就认为可以连边，层数就对应换乘次数。若 BFS 过程中到达了包含 destination 的线路，返回当前层数；如果无法到达，则返回 -1。
