@@ -335,6 +335,86 @@ IDA * 算法 对这一空间增长问题进行了优化,关于 IDA * 算法,
335335
336336### Java
337337
338+ ```java
339+ import java.util.PriorityQueue;
340+ import java.util.Scanner;
341+
342+ class Knight implements Comparable<Knight> {
343+ int x, y;
344+ int g, h, f;
345+
346+ public Knight(int x, int y, int g, int h, int f) {
347+ this.x = x;
348+ this.y = y;
349+ this.g = g;
350+ this.h = h;
351+ this.f = f;
352+ }
353+
354+ @Override
355+ public int compareTo(Knight k) {
356+ return Integer.compare(this.f, k.f);
357+ }
358+ }
359+
360+ public class Main {
361+ static int[][] moves = new int[1001][1001];
362+ static int[][] dir = { {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2} };
363+ static int b1, b2;
364+
365+ static int Heuristic(Knight k) {
366+ return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2);
367+ }
368+
369+ static void astar(Knight k) {
370+ PriorityQueue<Knight> que = new PriorityQueue<>();
371+ que.add(k);
372+ while (!que.isEmpty()) {
373+ Knight cur = que.poll();
374+ if (cur.x == b1 && cur.y == b2) {
375+ break;
376+ }
377+ for (int i = 0; i < 8; i++) {
378+ int nextX = cur.x + dir[i][0];
379+ int nextY = cur.y + dir[i][1];
380+ if (nextX < 1 || nextX > 1000 || nextY < 1 || nextY > 1000) {
381+ continue;
382+ }
383+ if (moves[nextX][nextY] == 0) {
384+ moves[nextX][nextY] = moves[cur.x][cur.y] + 1;
385+ Knight next = new Knight(nextX, nextY, cur.g + 5, Heuristic(new Knight(nextX, nextY, 0, 0, 0)), 0);
386+ next.f = next.g + next.h;
387+ que.add(next);
388+ }
389+ }
390+ }
391+ }
392+
393+ public static void main(String[] args) {
394+ Scanner scanner = new Scanner(System.in);
395+ int n = scanner.nextInt();
396+ while (n-- > 0) {
397+ int a1 = scanner.nextInt();
398+ int a2 = scanner.nextInt();
399+ b1 = scanner.nextInt();
400+ b2 = scanner.nextInt();
401+ for (int i = 0; i < 1001; i++) {
402+ for (int j = 0; j < 1001; j++) {
403+ moves[i][j] = 0;
404+ }
405+ }
406+ Knight start = new Knight(a1, a2, 0, Heuristic(new Knight(a1, a2, 0, 0, 0)), 0);
407+ start.f = start.g + start.h;
408+ astar(start);
409+ System.out.println(moves[b1][b2]);
410+ }
411+ scanner.close();
412+ }
413+ }
414+ ```
415+ 416+ 417+ 338418### Python
339419
340420``` Python
@@ -683,4 +763,3 @@ int main() {
683763
684764
685765
686-
0 commit comments