Leetcode 1142 Solution

This article provides solution to leetcode question 1142 (minimum-knight-moves)
Categories:
Tags:
Access this page by simply typing in "lcs 1142" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def minKnightMoves(self, target_x: int, target_y: int) -> int:
        q = collections.deque()
        visited = [[0 for _ in range(605)] for _ in range(605)]



        q.append((0, 0))
        visited[302][302] = 1



        step = -1
        while q:
            step += 1
            s = len(q)



            moves = [
                (1, 2),
                (-1, 2),
                (1, -2),
                (-1, -2),
                (2, 1),
                (-2, 1),
                (2, -1),
                (-2, -1),
            ]
            for _ in range(s):
                x, y = q.popleft()
                if x == target_x and y == target_y:
                    return step



                for dx, dy in moves:
                    new_x = x + dx
                    new_y = y + dy



                    if visited[new_x + 302][new_y + 302] == 0 and -302 <= new_x <= 302 and -302 <= new_y <= 302:
                        q.append((new_x, new_y))
                        visited[new_x + 302][new_y + 302] = 1



        return step