1197. Minimum Knight Moves - cocoder39/coco39_LC GitHub Wiki

1197. Minimum Knight Moves

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        DIR = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
        
        queue = collections.deque([(0, 0)])
        visited = set([(0, 0)])
        step = 0
        while queue:
            n = len(queue)
            for i in range(n):
                cur_x, cur_y = queue.popleft()
                if cur_x == x and cur_y == y:
                    return step
                for dx, dy in DIR:
                    next_x, next_y = cur_x + dx, cur_y + dy
                    if (next_x, next_y) not in visited:
                        visited.add((next_x, next_y))
                        queue.append((next_x, next_y))
            step += 1
        return -1