LC 1197 [M] Minimum Knight Moves - ALawliet/algorithms GitHub Wiki

DIRS = [(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        Q = deque([ (0,0) ])
        
        seen = set()
        seen.add( (0,0) )
        
        # limit top right corner so we can check the bounds and not worry about other positions cause they are symmetric (board is symmetric)
        x = abs(x)
        y = abs(y)
        
        steps = 0
        
        while Q:
            for _ in range(len(Q)):
                r, c = Q.popleft()
                
                if r == x and c == y:
                    return steps
                
                for dr, dc in DIRS:
                    nr = r + dr
                    nc = c + dc
                    
                    # extend bounds by 2 to let the knight jump off by offset 2 so it can jump back
                    if (nr, nc) not in seen and -2 <= nr <= x + 2 and -2 <= nc <= y + 2:
                        Q.append( (nr, nc) )
                        seen.add( (nr, nc) )
                
            steps += 1