AcWing 1102.移动骑士 Java版

import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int N = 310;
    static int n;//n∗n的棋盘
    static int[][] d; // 记录该点到起始点的距离
    static Pair[] q; // 记录探索的坐标
    static int hh, tt;//hh表示队头，tt表示队尾

    public static class Pair {
        int x, y;
        public Pair(int first, int second) {
            this.x = first;
            this.y = second;
        }
    }

    static void solution() {
        n = sc.nextInt();
        int strx = sc.nextInt(), stry = sc.nextInt();
        int endx = sc.nextInt(), endy = sc.nextInt();
        if (strx == endx && stry == endy) { // 早退条件
            System.out.println(0);
            return;
        }
        // 初始化
        d = new int[n + 10][n + 10];
        q = new Pair[N * N];
        hh = tt = 0;

        q[tt++] = new Pair(strx, stry); // 将起点加入队列
        bfs(endx, endy); // 执行 BFS
    }

    static void bfs(int endx, int endy) {
        //骑士移动的8个方向
        int[] xx = {-2, -2, -1, -1, 1, 1, 2, 2};
        int[] yy = {-1, 1, -2, 2, -2, 2, -1, 1};

        // 队列中还有元素
        while (hh < tt) {
            Pair t = q[hh++];//出队
            for (int i = 0; i < 8; i++) {
                int x = t.x + xx[i];
                int y = t.y + yy[i];
                if (check(x, y) && d[x][y] == 0) { // 合法且未访问
                    d[x][y] = d[t.x][t.y] + 1;
                    q[tt++] = new Pair(x, y);
                    if (x == endx && y == endy) { // 终点条件
                        System.out.println(d[x][y]);
                        return;
                    }
                }
            }
        }
    }

    // 判断点(x,y)是否合法
    public static boolean check(int x, int y) {
        if(x>=0&&x<n&&y>=0&&y<n) return true;
        return false;
    }

    public static void main(String[] args) {
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            solution();
        }
    }
}