代码随想录Day76（图论Part11）

97.小明逛公园（Floyd）

题目：97. 小明逛公园 (kamacoder.com)

思路：

答案

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();  // 顶点数int m = scanner.nextInt();  // 边数int[][] grid = new int[n + 1][n + 1];final int INF = 10005; // 因为边的最大距离是10^4// 初始化图的邻接矩阵for (int i = 1; i <= n; i++) {Arrays.fill(grid[i], INF);grid[i][i] = 0; // 自己到自己的距离为0}// 读取边的信息并填充邻接矩阵for (int i = 0; i < m; i++) {int p1 = scanner.nextInt();int p2 = scanner.nextInt();int val = scanner.nextInt();grid[p1][p2] = val;grid[p2][p1] = val; // 注意这里是双向图}// 开始 Floyd-Warshall 算法for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {grid[i][j] = Math.min(grid[i][j], grid[i][k] + grid[k][j]);}}}// 读取查询并输出结果int z = scanner.nextInt(); // 查询次数while (z-- > 0) {int start = scanner.nextInt();int end = scanner.nextInt();if (grid[start][end] == INF) {System.out.println(-1);} else {System.out.println(grid[start][end]);}}scanner.close();}
}

小结

126.骑士的攻击（A*算法）

题目：126. 骑士的攻击 (kamacoder.com)

思路：毫无疑问是最难的一题

答案

import java.util.*;class Knight implements Comparable<Knight> {int x, y, g, h, f;public Knight(int x, int y, int g, int h) {this.x = x;this.y = y;this.g = g;this.h = h;this.f = g + h;}@Overridepublic int compareTo(Knight k) {return Integer.compare(this.f, k.f); // 从小到大排序}
}public class Main {static int[][] moves = new int[1001][1001];static int[][] dir = {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2},{2, 1}, {2, -1}, {1, -2}, {-1, -2}};static int b1, b2;static PriorityQueue<Knight> que = new PriorityQueue<>();public static int heuristic(Knight k) {return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2); // 统一不开根号，这样可以提高精度}public static void astar(Knight start) {que.add(start);while (!que.isEmpty()) {Knight cur = que.poll();if (cur.x == b1 && cur.y == b2)break;for (int i = 0; i < 8; i++) {int nextX = cur.x + dir[i][0];int nextY = cur.y + dir[i][1];if (nextX < 1 || nextX > 1000 || nextY < 1 || nextY > 1000)continue;if (moves[nextX][nextY] == 0) {moves[nextX][nextY] = moves[cur.x][cur.y] + 1;int nextG = cur.g + 5; // 马走日，1 * 1 + 2 * 2 = 5int nextH = heuristic(new Knight(nextX, nextY, 0, 0));que.add(new Knight(nextX, nextY, nextG, nextH));}}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();while (n-- > 0) {int a1 = scanner.nextInt();int a2 = scanner.nextInt();b1 = scanner.nextInt();b2 = scanner.nextInt();for (int[] row : moves) Arrays.fill(row, 0);Knight start = new Knight(a1, a2, 0, heuristic(new Knight(a1, a2, 0, 0)));astar(start);que.clear(); // 清空队列System.out.println(moves[b1][b2]);}scanner.close();}
}