Shortest Knight Path

Given an ( n \times n ) chessboard and the starting position ((s_x, s_y)) of a knight along with a target position ((t_x, t_y)), determine the minimum number of moves required for the knight to reach the target using standard chess knight moves. The knight's move is defined by the possible displacements: ( (\pm2, \pm1) ) and ( (\pm1, \pm2) ). If the knight cannot reach the target, return -1. If the starting position is the same as the target, the answer is 0.

Note: The board is represented by ( n ) strings each of length ( n ), where the starting cell contains a 'K' and the remaining cells are filled with dots ('.'). Although the board is provided as input, there are no obstacles other than board limits, so only the boundaries of the board restrict the knight’s movement.

The movement rules can be summarized by the following formulas for a move from a cell ( (x, y) ): [ (x, y) \rightarrow (x+\delta_x, y+\delta_y) \quad \text{for} \quad (\delta_x, \delta_y) \in { (2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1) } ]

inputFormat

Standard input is used. The first line contains an integer ( n ) representing the board's size. The second line contains two integers ( s_x ) and ( s_y ) indicating the knight's starting coordinates. The third line contains two integers ( t_x ) and ( t_y ) indicating the target's coordinates. This is followed by ( n ) lines, each containing a string of length ( n ) representing the board. The board's first occurrence of 'K' is at the starting position.

outputFormat

Print a single integer to standard output: the minimum number of moves required for the knight to reach the target. If the target is unreachable, print -1.## sample

3
0 0
2 2
K..
...
...

4