Problem description:

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.

https://assets.leetcode.com/uploads/2018/10/12/knight.png

Return the minimum number of steps needed to move the knight to the square [x, y]. It is guaranteed the answer exists.

Example 1:

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

Example 2:

1
2
3
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

Solution:

Regular BFS

However, since the matrix is symmetric, we could downgrade the destination (x,y) .

Once the (x,y) is smaller, then we use BFS to compute

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        # memo + bfs
        visited = set((0,0,0)) # i, j, moves
        q = deque([(0,0,0)])
        res = 0
        x, y = abs(x), abs(y)
        while x > 4 or y > 4:
            res += 1
            if x >= y:
                x -= 2
                y = abs(y-1) 
            else:
                x -= 1 if x >= 1 else -1
                y -= 2 
        
        print(x, y)
        while q:
            i, j, move = q.popleft()
            if i == x and j == y:
                return res+move
            for nx, ny in [(i-2,j-1), (i-1,j-2), (i-2,j+1), (i-1,j+2),
                           (i+2,j-1), (i+1,j-2), (i+2,j+1), (i+1,j+2)]:
                if (nx,ny,move+1) not in visited:
                    q.append((nx,ny,move+1))
        return -1

time complexity: $O()$
space complexity: $O()$
reference:
related problem: