信息学奥赛一本通T1450-Knight Moves-题解（Java代码）

解题思路：以为很难，没想到就是走迷宫的原题 就是方向变了

import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] direction = { { -1, -2 }, { -2, -1 }, { -2, 1 }, { -1, 2 },
                { 1, -2 }, { 2, -1 }, { 2, 1 }, { 1, 2 } };
        for (int i = 0; i < n; i++) {
            int L = sc.nextInt();
            int[][] arr = new int[L + 1][L + 1];
            int startx = sc.nextInt();
            int starty = sc.nextInt();
            int endx = sc.nextInt();
            int endy = sc.nextInt();
            if (startx == endx && endy == starty) {
                System.out.println(0);
                continue;
            }
            int k = 0;
            boolean iRet = true;
            LinkedList<nnn> queue = new LinkedList<nnn>();
            queue.add(new nnn(startx, starty, 0));
            arr[startx][starty] = 1;
            while (!queue.isEmpty()) {
                nnn d = queue.poll();
                k = d.step;
                if (d.x == endx && d.y == endy) {
                    System.out.println(d.step);
                    iRet = false;
                    break;
                }
                for (int j = 0; j < direction.length; j++) {
                    int x = d.x + direction[j][0];
                    int y = d.y + direction[j][1];
                    if (x >= 0 && y >= 0 && x < L && y < L && arr[x][y] == 0) {
                        arr[x][y] = 1;
                        queue.addLast(new nnn(x, y, d.step + 1));
                    }
                }
            }
            if(iRet)System.out.println(k);
        }
    }

}

class nnn {
    public int x;
    public int y;
    public int step;

    public nnn(int x, int y, int step) {
        this.x = x;
        this.y = y;
        this.step = step;
    }
}