Knight Minimum Moves
mediumGraphs II+20 XPTime limit 3s
A chess knight stands on square (a, b) of an n × n board (rows and columns numbered 1 … n). A knight moves in an "L": two squares in one direction and one square at a right angle — up to 8 possible moves, and it may never leave the board. What is the minimum number of moves to reach square (x, y)?
Input: one line n a b x y.
Output: the minimum number of moves, or -1 if the target cannot be reached.
Constraints: 1 ≤ n ≤ 300, 1 ≤ a, b, x, y ≤ n.
Think about it: squares are nodes and knight moves are edges, all of cost 1 — so BFS from the start gives the answer. Mark a square visited when you push it, and stop as soon as you reach the target. On tiny boards (n = 2 or 3) some squares are unreachable.
Sample input 1
8 1 1 8 8
Sample output 1
6
Sample input 2
3 1 1 2 2
Sample output 2
-1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).