1020. Minimum Moves to Reach Target in Knight Moves

On an n x n chessboard with cells labeled by [row, col], a knight starts at 'start' and wants to reach 'target'. Return the minimum number of knight moves needed, or -1 if the target is unreachable. The input is JSON {n, start, target}.

Input: JSON {n, start, target}.

Output: Integer — minimum knight moves, or -1.

Examples

Input: {"n":8,"start":[0,0],"target":[2,1]}
Output: 1
Explanation: One knight move.

Input: {"n":8,"start":[0,0],"target":[7,7]}
Output: 6
Explanation: Six moves across the board.

Input: {"n":5,"start":[2,2],"target":[2,2]}
Output: 0
Explanation: Already there.

Constraints

• 1<=n<=300
• start/target on the board

Asked by