NCEA Scholarship 2025 Digital Technologies Q2 (Sample)

You are given a challenge to calculate the minimum number of moves a knight takes to get from a target position to a destination. You are given the size of the chess board and a series of queries. Each query lists two squares on the board, the starting position and the target position. You are required to give the minimum number of moves needed for a knight to move between these positions. As a reminder, the knight moves in an L shape, moving one square in one direction and two in the other; the knight cannot move out of the board.

Input

The first line of input will be single integer $N$

denoting a chess board of size $N\times N$ where $4\le N\le 100$.

The following lines will contain a series of queries, of the form

$a,b,c,d$ where $\left(a,b\right)$ and $\left(c,d\right)$ are the two squares you need to move the knight between. Note that $1\le a,b,c,d \le N$

The input will be terminated by the line:

0 0 0 0

There will be at most 100 queries per test case.

Output

For each query you should output a single integer, the minimum number of knight moves to traverse between the two squares.

This question is taken with permission from Scholarship Digital Technologies 93604 (Sample assessment 2025). However, subtasks and test data (with the exception of the sample data) are created independently by the NZOI. Your result is no indication of exam performance. These questions are unlikely to be sufficient preparation for the exam. NZQA owns the copyright in the examination material reproduced, and has consented to its reproduction, but takes no responsibility for its accuracy or fitness for purpose. The performance standard by which the scholarship assessments are assessed, varies significantly from the NZOI grading and selection process, and success in the NZOI selection process does not guarantee gaining a Scholarship in Digital Technologies. This question cannot be reproduced by any means without the prior permission of NZQA.

Submission

For our site, go to the submit tab to upload your solution.

Please note: If you're using Python, submit your solution with Python 3.6 (PyPy 7.3). Python 3.8 will be too slow.

Subtasks

• Subtask 1 (5%): $N=4$.
• Subtask 2 (5%): $N=5$.
• Subtask 3 (40%): $N=20$.
• Subtask 4 (45%): $N=100$.
• Subtask 5 (5%): $N=1,000,000,000$. This subtask is extra for experts and exceeds the bounds given in the question. We assume it would not be expected for you to present this solution in an exam.