815. 公交路线
我们有一系列公交路线。每一条路线 routes[i] 上都有一辆公交车在上面循环行驶。例如，有一条路线 routes[0] = [1, 5, 7]，表示第一辆 (下标为0) 公交车会一直按照 1->5->7->1->5->7->1->… 的车站路线行驶。
假设我们从 S 车站开始（初始时不在公交车上），要去往 T 站。 期间仅可乘坐公交车，求出最少乘坐的公交车数量。返回 -1 表示不可能到达终点车站。
示例:
输入:
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
输出: 2
解释:
最优策略是先乘坐第一辆公交车到达车站 7, 然后换乘第二辆公交车到车站 6。
说明:
1 <= routes.length <= 500.
1 <= routes[i].length <= 500.
0 <= routes[i][j] < 10 ^ 6.
import java.awt.Point;
class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
if (S == T) {
return 0;
}
int numsOfBus = routes.length;
List<List<Integer>> busGraph = new ArrayList<>();
for (int i = 0; i < numsOfBus; i++) {
Arrays.sort(routes[i]);
busGraph.add(new ArrayList<>());
}
//把有相同站点的车联系起来
for (int i = 0; i < numsOfBus; i++) {
for (int j = i + 1; j < numsOfBus; j++) {
if (intersect(routes[i], routes[j])) {
busGraph.get(i).add(j);
busGraph.get(j).add(i);
}
}
}
Queue<int[]> queue = new LinkedList<>();
List<Integer> seen = new ArrayList<>();
List<Integer> targets = new ArrayList<>();
// 包含起点的加入起始队列，包含目的地的加入目标队列
// seen用来确保
for (int i = 0; i < numsOfBus; i++) {
if (Arrays.binarySearch(routes[i], S) >= 0) {
seen.add(i);
queue.add(new int[]{i, 0});
}
if (Arrays.binarySearch(routes[i], T) >= 0) {
targets.add(i);
}
}
//BFS走起
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int busLine = cur[0];
int depth = cur[1];
if (targets.contains(busLine)) {
return depth + 1;
}
List<Integer> neighbors = busGraph.get(busLine);
for (int k = 0; k < neighbors.size(); k++) {
if (!seen.contains(neighbors.get(k))) {
seen.add(neighbors.get(k));
queue.add(new int[]{neighbors.get(k), depth + 1});
}
}
}
return -1;
}
private boolean intersect(int[] route1, int[] route2) {
int len1 = route1.length;
int len2 = route2.length;
int i = 0;
int j = 0;
while (i < len1 && j < len2) {
if (route1[i] == route2[j]) {
return true;
}
if (route1[i] > route2[j]) {
j++;
}
else
{
i++;
}
}
return false;
}
}