390. Knight to the Far Corner
A knight stands on an n by n chessboard. It moves in an L: two squares one
way and one square the other, eight possibilities in all, and it may not leave
the board.
Print the fewest moves to get from the starting square to the target square, or
-1 if it cannot be done.
There is no grid of walls to read here, and that is the point. The board is the graph: squares are vertices and the eight L-moves are the edges. Once you see that, this is the breadth-first search of problem 375 with a different list of offsets.
Rows and columns are numbered 1 to n.
One case is worth predicting before you code it. On a 3 by 3 board the knight can never reach the centre square from anywhere, because every L-move from the centre leaves the board.
Constraints - `1 ≤ n ≤ 300` - `1 ≤ sr, sc, tr, tc ≤ n`
Input
One line containing five integers n, sr, sc, tr and tc: the board
size, the starting row and column, and the target row and column. Rows and
columns are numbered 1 to n.
Output
Print one integer, the fewest moves, or -1 if the target cannot be reached.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.