In an **infinite** chess board with coordinates from `-infinity`

to `+infinity`

, you have a **knight** at square `[0, 0]`

.

A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Return the minimum number of steps needed to move the knight to the square `[x, y]`

. It is guaranteed the answer exists.

**Example 1:**

Input:x = 2, y = 1Output:1Explanation:[0, 0] → [2, 1]

**Example 2:**

Input:x = 5, y = 5Output:4Explanation:[0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

class Solution: def minKnightMoves(self, x: int, y: int) -> int: x, y = abs(x), abs(y) q = collections.deque([(0,0,0)]) seen = set([(0,0)]) while q: s_x, s_y, s = q.popleft() if (s_x, s_y) == (x,y): return s d = [] for dx, dy in [(-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2)]: n_x = s_x + dx n_y = s_y + dy if -2 <= n_x <= x and -2 <= n_y <= y: d.append((n_x,n_y)) d.sort(key=lambda e: abs(x-e[0]) + abs(y-e[1])) # only enqueue towards the 2 directions closest to the x,y for n_x,n_y in d[:2]: if (n_x, n_y) not in seen: q.append((n_x,n_y,s+1)) seen.add((n_x,n_y))