BOJ. Move the Knight (7562)

Problem link

For each test case, find the minimum number of knight moves between two squares on an L × L chessboard. Each move changes one coordinate by 1 and the other by 2, with either sign, and the knight must remain on the board.

Treat every board square as a graph vertex and each legal knight move as an edge. Since all edges have equal cost, breadth-first search (BFS) visits squares in nondecreasing distance from the start. The first time the target is discovered therefore gives the shortest path length. The distance matrix also marks visited squares: a square is enqueued only while its distance is -1, so it enters the queue at most once. If start and target are the same square, the answer is zero.

The input scanner accepts arbitrary whitespace, and the primitive queue is reused for every test case. A board has L² squares and at most eight outgoing moves per square, so the time complexity is O(L²) and the auxiliary space complexity is O(L²).

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    private static final int[] DR = {-2, -2, -1, -1, 1, 1, 2, 2};
    private static final int[] DC = {-1, 1, -2, 2, -2, 2, -1, 1};

    public static void main(String[] args) throws IOException {
        FastScanner in = new FastScanner();
        int testCases = in.nextInt();
        int[] queue = new int[300 * 300];
        StringBuilder answer = new StringBuilder();

        for (int test = 0; test < testCases; test++) {
            int length = in.nextInt();
            int startRow = in.nextInt();
            int startCol = in.nextInt();
            int targetRow = in.nextInt();
            int targetCol = in.nextInt();
            int[][] distance = new int[length][length];
            for (int row = 0; row < length; row++) {
                for (int col = 0; col < length; col++) {
                    distance[row][col] = -1;
                }
            }

            int head = 0;
            int tail = 0;
            int start = startRow * length + startCol;
            int target = targetRow * length + targetCol;
            distance[startRow][startCol] = 0;
            queue[tail++] = start;

            while (head < tail && distance[targetRow][targetCol] == -1) {
                int square = queue[head++];
                int row = square / length;
                int col = square % length;
                for (int move = 0; move < 8; move++) {
                    int nextRow = row + DR[move];
                    int nextCol = col + DC[move];
                    if (nextRow < 0 || nextRow >= length
                            || nextCol < 0 || nextCol >= length
                            || distance[nextRow][nextCol] != -1) {
                        continue;
                    }
                    distance[nextRow][nextCol] = distance[row][col] + 1;
                    queue[tail++] = nextRow * length + nextCol;
                }
            }
            answer.append(distance[targetRow][targetCol]).append('\n');
        }

        System.out.print(answer);
    }

    private static final class FastScanner {
        private final BufferedInputStream in = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int pointer;
        private int length;

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value;
        }

        private int read() throws IOException {
            if (pointer == length) {
                length = in.read(buffer);
                pointer = 0;
                if (length == -1) {
                    return -1;
                }
            }
            return buffer[pointer++];
        }
    }
}