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;
}
@Override
public 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 = 5
int 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();
}
}