# Minimum Knight Moves

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 = 1
Output: 1
Explanation: [0, 0] → [2, 1]
```

Example 2:

```Input: x = 5, y = 5
Output: 4
Explanation: [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) + abs(y-e))

# 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))