# LeetCode 1197. Minimum Knight Moves

## 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 = 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:

• `-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).

## One Thought to “LeetCode 1197. Minimum Knight Moves”

1. If you are a regular Linux user or a system administrator, you might require to set up networking on your system. Unlike the desktop systems whereread more , with screen shot and code snipets at
Network Configuration in Debian 11