Problem statement

https://leetcode.com/problems/minimum-knight-moves/

Solution

We can solve this problem with classical bfs.

Complexity

Time complexity is potentially upto O(x*y), with quite big constant, space complexity as well.

Code

class Solution:
    def minKnightMoves(self, x, y):
        queue = deque([(0, 0, 0)])
        dirs = [(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1)]
        V = set((0, 0))
        
        while queue:
            steps, i, j = queue.popleft()
            if (x, y) == (i, j): return steps
            V.add((i, j))
            for dx, dy in dirs:
                if (i + dx, j + dy) in V: continue
                V.add((i + dx, j + dy))
                queue.append((steps + 1, i + dx, j + dy))

Remark

It is also possible to solve this problem with dp. There is also direct formula in O(1) can be derived!