문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

출력

첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

예제1 - 입력

7
6 6 0 1

예제1 - 출력

4

예제2 - 입력

6
5 1 0 5

예제2 - 출력

-1

예제3 - 입력

7
0 3 4 3

예제3 - 출력

2

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        int n = Integer.parseInt(br.readLine());

        int[][] map = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(map[i], -1);
        }
        StringTokenizer st = new StringTokenizer(br.readLine());

        Pair now = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        Pair dest = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

        int[] mx = {-2, -2, 0, 0, 2, 2};
        int[] my = {-1, 1, -2, 2, -1, 1};

        Queue<Pair> queue = new LinkedList<>();
        queue.offer(now);
        map[now.x][now.y] = 0;

        while (!queue.isEmpty()) {
            now = queue.poll();
            if (now.x == dest.x && now.y == dest.y)
                break;

            for (int i = 0; i < mx.length; i++) {
                int tx = now.x + mx[i];
                int ty = now.y + my[i];

                if ((tx >= 0 && tx < n) && (ty >= 0 && ty < n)) {
                    if (map[tx][ty] == -1) {
                        map[tx][ty] = map[now.x][now.y] + 1;
                        queue.offer(new Pair(tx, ty));
                    }
                }
            }
        }

        System.out.println(map[dest.x][dest.y]);
    }
    static class Pair {
        public int x;
        public int y;

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