# 1197. 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]

Constraints:
|x| + |y| <= 300

# Solution

Approach 1: BFS.

# Code (Python)

Approach 1:

    def minKnightMoves(self, x: int, y: int) -> int:
        # BFS -- optimized by pruning coordinates in the wrong directions
        if x == 0 and y == 0:
            return 0
        queue = deque([(0, 0, 0)])
        added = set([(0, 0)])
        while queue:
            position = queue.popleft()
            for delta in [(1, 2), (2, 1), (2, -1), (1, -2), (-1, 2), (-2, 1), (-2, -1), (-1, -2)]:
                new_x, new_y = position[0] + delta[0], position[1] + delta[1]
                if new_x == x and new_y == y:
                    return position[2] + 1
                if (new_x, new_y) in added:
                    continue
                added.add((new_x, new_y))
                if new_x * x < 0 or new_y * y < 0:
                    # about the right direction
                    continue
                queue.append((new_x, new_y, position[2] + 1))
        return -1

# Code (C++)

Approach 1:

Approach 2: