Noodling with Knights
Description
After eating a bunch of noodles, the mad hatters decide that it's time to play a quick game of chess. They play a special variant of chess where the board is completely empty except for a single knight. Furthermore, they decide that this game is too boring, so they want to play on arbitrary-sized square chess boards, not just $8 \times 8$.
Given a chess board of size $N \times N$, and a knight starting at position $(x_1, y_1)$, how many steps at minimum would it take for it to reach position $(x_2, y_2)$?
If the position is not reachable, output $-1$.
Constraints:
$0 < N < 800$
$0 < x_i, y_i < N$
The first line of the input will contain just one number, N. The second line will contain two integers, $x_1$ and $y_1$, the starting position of the knight. The third line will contain three integers $x_2$ and $y_2$, the end position of the knight.
The output will consist of a single integer, which is the minimum number of moves the knight needs to make to reach the end position.
If the position is not reachable, output -1.
Input
The first line of the input will contain just one number, N. The second line will contain two integers, $x_1$ and $y_1$, the starting position of the knight. The third line will contain three integers $x_2$ and $y_2$, the end position of the knight.
Output
The output will consist of a single integer, which is the minimum number of moves the knight needs to make to reach the end position.
If the position is not reachable, output -1.
1
0 0
0 0
4
1 2
2 2
9
8 2
4 1
0
3
3