A chess enthusiast on Lamia's team wonders: what's the minimum number of knight moves between two arbitrary squares on an infinite board? On an infinite chessboard, given a knight's start (x1,y1) and target (x2,y2), print the minimum number of knight moves to reach the target. Use BFS with pruned bounds around the two points.
Input
Four integers x1 y1 x2 y2.
Output
Minimum number of knight moves.
Constraints
-300 ≤ coords ≤ 300
Sample Input
0 0 3 3
Sample Output
2
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.