A knight stands on square [0, 0] of a chessboard that goes on forever in every direction, so negative coordinates are squares too. In one move the knight jumps two squares along one axis and one square along the other: from [a, b] it can reach [a ± 2, b ± 1] or [a ± 1, b ± 2], eight squares in all.
Return the fewest moves the knight needs to land on square [x, y]. Every square can be reached.
Example 1
Input: x = -3, y = 3
Output: 2
[0, 0] → [-1, 2] → [-3, 3]. No single move covers 3 squares along both axes, so two is the fewest.
Example 2
Input: x = 0, y = 1
Output: 3
The target is right next to the start, yet it takes three moves, for example [0, 0] → [1, 2] → [-1, 3] → [0, 1]. Neither one move nor two can end there.
Example 3
Input: x = 6, y = -4
Output: 4
One shortest route is [0, 0] → [2, 1] → [3, -1] → [4, -3] → [6, -4].
Constraints
-300 <= x, y <= 3000 <= |x| + |y| <= 300Every move costs the same, so a breadth-first search from [0, 0] reaches each square in the fewest moves. The first time the search reaches [x, y], the number of rounds so far is the answer.
-3
2