문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

풀이

import java.io.*;
import java.util.*;
public class Main {
    static int N;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = { 2, 2, 1, -1, -2, -2, 1, -1 };
    static int[] dy = { 1, -1, 2, 2,  1, -1, -2, -2};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        while(T-- > 0) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            arr = new int[N][N];

            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            Node start = new Node(x, y);

            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            Node end = new Node(x, y);

            visited = new boolean[N][N];
            int result = BFS(start, end);
            System.out.println(result);

        }
    }
    public static int BFS(Node start, Node end) {
        Queue<Node> q = new LinkedList<>();
        q.add(start);
        visited[start.x][start.y] = true;
        while(!q.isEmpty()) {
            Node n = q.poll();
            if (n.x == end.x && n.y == end.y)
                return arr[n.x][n.y];
            for (int i = 0; i < 8; i++) {
                int nx = n.x + dx[i];
                int ny = n.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N)
                    continue;
                if (visited[nx][ny])
                    continue;
                visited[nx][ny] = true;
                arr[nx][ny] = arr[n.x][n.y] + 1;
                q.add(new Node(nx, ny));
            }
        }
        return -1;
    }

}
class Node {
    int x, y;
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}