문제

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

입력

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

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

출력

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

예제1-입력

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제1 - 출력

5
28
0

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int tc = Integer.parseInt(br.readLine());

        while (tc -- > 0){
            int n = Integer.parseInt(br.readLine());
            int[][] board = new int[n][n];

            StringTokenizer st = new StringTokenizer(br.readLine());
            Pair str = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

            st = new StringTokenizer(br.readLine());
            Pair dest = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

            int[] mx = {-2, -1, 1, 2, 2, 1, -1, -2};
            int[] my = {-1, -2, -2, -1, 1, 2, 2, 1};
            for(int i = 0; i < n; i++)
                Arrays.fill(board[i], n * n);

            Queue<Pair> queue = new LinkedList<>();
            board[str.x][str.y] = 0;
            queue.add(str);
            while (!queue.isEmpty()){
                Pair now = queue.poll();

                for(int i = 0; i < mx.length; i++){
                    int dx = now.x + mx[i];
                    int dy = now.y + my[i];
                    if((dx >= 0 && dx < n) && (dy >= 0 && dy < n)){
                        if(board[dx][dy] == n * n) {
                            board[dx][dy] = board[dx][dy] <= board[now.x][now.y] + 1 ? board[dx][dy] : board[now.x][now.y] + 1;
                            queue.add(new Pair(dx, dy));
                        }
                    }
                }
            }
            bw.append(board[dest.x][dest.y] + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
    static class Pair{
        public int x;
        public int y;
        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}