## Description

https://leetcode.com/problems/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 = 1Output:1Explanation:[0, 0] → [2, 1]

**Example 2:**

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

**Constraints:**

`-300 <= x, y <= 300`

`0 <= |x| + |y| <= 300`

## Python Solution

Use breadth-first search to how many steps to reach the target position.

```
class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
DIRECTIONS = [
(-2, -1), (-2, 1), (-1, 2), (1, 2),
(2, 1), (2, -1), (1, -2), (-1, -2)
]
queue = deque()
queue.append((0, 0))
distance_dict = {(0, 0): 0}
while queue:
i, j = queue.popleft()
if (i, j) == (x, y):
return distance_dict[(i, j)]
for dx, dy in DIRECTIONS:
next_i, next_j = i + dx, j + dy
if (next_i, next_j) in distance_dict:
continue
queue.append((next_i, next_j))
distance_dict[(next_i, next_j)] = distance_dict[(i, j)] + 1
return -1
```

- Time Complexity: O(N).
- Space Complexity: O(N).