815. 公交路线

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

  • 例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> … 这样的车站路线行驶。

现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

示例 1：
输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6 输出：2 解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
示例 2：
输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12 输出：-1

提示：

  • 1 <= routes.length <= 500.
  • 1 <= routes[i].length <= 105
  • routes[i] 中的所有值 互不相同
  • sum(routes[i].length) <= 105
  • 0 <= routes[i][j] < 106
  • 0 <= source, target < 106

思路：
如何建图？
考虑将每条公交路线看作一个点
即找从所有包含源点公交站的公交路线到所有包含终点公交站的所有公交路线的最短距离
只要任意两条路线有相同的公交站，说明相互可达。

  1. class Solution {
  2.     public int numBusesToDestination(int[][] routes, int source, int target) {
  3.         int n = routes.length;
  4.         if (source == target) return 0;
  5.         boolean[][] st = new boolean[n][n];
  6.         Map<Integer, List<Integer>> map = new HashMap<>();
  8.         for (int i = 0; i < n; i++) {
  9.             for (int x : routes[i]) {
  10.                 List<Integer> t = map.getOrDefault(x, new ArrayList<>());
  11.                 for (int j : t) {
  12.                     st[i][j] = st[j][i] = true;
  13.                 }
  14.                 t.add(i);
  15.                 map.put(x, t);
  16.             }
  17.         }
  19.         int[] d = new int[n];
  20.         Arrays.fill(d, 0x3f3f3f3f);
  21.         Queue<Integer> q = new LinkedList<>();
  22.         for (int x : map.get(source)) {
  23.             d[x] = 1;
  24.             q.offer(x);
  25.         }
  27.         while (!q.isEmpty()) {
  28.             int u = q.poll();
  29.             for (int i = 0; i < n; i++) {
  30.                 if (i == u) continue;
  31.                 if (st[i][u] && d[i] > d[u] + 1) {
  32.                     d[i] = d[u] + 1;
  33.                     q.offer(i);
  34.                 }
  35.             }
  36.         }
  38.         int min = 0x3f3f3f3f;
  39.         for (int x : map.getOrDefault(target, new ArrayList<>()))
  40.             min = Math.min(min, d[x]);
  41.         return min == 0x3f3f3f3f ? -1: min;
  42.     }
  43. }

Acwing 3675. 逃离迷宫

image.png

思路：本质是单源最短路问题
不同点在于可将每条长或宽看作一个点，每条边为拐弯一次。

  1. import java.util.*;
  3. public class Main {
  4.     static final int INF = 0x3f3f3f3f, N = 110;
  5.     static int n, m;
  6.     static char[][] c = new char[N][];
  7.     static int[][] res = new int[N][N];
  8.     static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
  9.     static boolean[][] st = new boolean[N][N];
  10.     public static void main(String[] args) {
  11.         Scanner sc = new Scanner(System.in);
  12.         int T = sc.nextInt();
  13.         while (T-- > 0) {
  14.             n = sc.nextInt();
  15.             m = sc.nextInt();
  16.             for (int i = 1; i <= n; i++)
  17.                 c[i] = (" " + sc.next()).toCharArray();
  18.             for (int i = 1; i <= n; i++) {
  19.                 Arrays.fill(res[i], 1, m + 1, INF);
  20.                 Arrays.fill(st[i], 1, m + 1, false);
  21.             }
  22.             int k = sc.nextInt();
  23.             int sx, sy, ex, ey;
  24.             sy = sc.nextInt();
  25.             sx = sc.nextInt();
  26.             ey = sc.nextInt();
  27.             ex = sc.nextInt();
  28.             res[sx][sy] = -1;
  30.             Queue<int[]> q = new LinkedList<>();
  31.             q.offer(new int[]{sx, sy, -1});
  32.             st[sx][sy] = true;
  33.             while (!q.isEmpty()) {
  34.                 int[] p = q.poll();
  35.                 int x = p[0], y = p[1], t = p[2];
  36.                 for (int i = 0; i < 4; i++) {
  37.                     int a = x + dx[i], b = y + dy[i];
  38.                     while (a >= 1 && a <= n && b >= 1 && b <= m && c[a][b] == '.') {
  39.                         if (!st[a][b]) {
  40.                             res[a][b] = t + 1;
  41.                             st[a][b] = true;
  42.                             q.offer(new int[]{a, b, t + 1});
  43.                         }
  44.                         a = a + dx[i];
  45.                         b = b + dy[i];
  46.                     }
  47.                 }
  48.             }
  50.             // for (int i = 1; i <= n; i++) {
  51.             //     for (int j = 1; j <= m; j++) {
  52.             //         System.out.printf("%-10d ", res[i][j]);
  53.             //     }
  54.             //     System.out.println();
  55.             // }
  56.             // System.out.println(res[ex][ey] + " " + k);
  57.             if (res[ex][ey] <= k)
  58.                 System.out.println("yes");
  59.             else System.out.println("no");
  60.         }
  61.     }
  62. }