pylist

1197. Minimum Knight Moves

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.

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

Example 1:

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

Example 2:

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

Constraints:

Solution

Code Steps

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        # combine similar cases
        x = abs(x)
        y = abs(y)
        # queue from the start
        q_s = deque([(0, 0)])
        qed_s = set(q_s)
        # queue from the end
        q_e = deque([(x, y)])
        qed_e = set(q_e)
        # step counter
        step = 0
        while True:
            # one layer from the start
            for i in range(len(q_s)):
                node = q_s.popleft()
                # return condition: meet the other side
                if node in qed_e:
                    return step
                for nei in self.find_nei(node):
                    if nei not in qed_s:
                        q_s.append(nei)
                        qed_s.add(nei)
            step += 1
            # one layer from the end
            for i in range(len(q_e)):
                node = q_e.popleft()
                if node in qed_s:
                    return step
                for nei in self.find_nei(node):
                    if nei not in qed_e:
                        q_e.append(nei)
                        qed_e.add(nei)
            step += 1
                        
    def find_nei(self, node):
        alter = [
            (1, 2),
            (2, 1),
            (-1, 2),
            (2, -1),
            (1, -2),
            (-2, 1),
            (-1, -2),
            (-2, -1),
        ]
        nei = [
            tuple(node[i] + a[i] for i in range(2))
            for a in alter
        ]
        # remove obvious wrong answer
        nei = [
            n for n in nei
            if n[0] > -2
            and n[1] > -2
        ]
        return nei

要点

Over timed Solution

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        q = deque([(0, 0)])
        qed = set(q)
        step = 0 # special case, end is start
        while True:
            for i in range(len(q)):
                # pop
                node = q.popleft()
                # process
                if node == (x, y):
                    return step
                # add nei
                for nei in self.find_nei(node):
                    if nei not in qed:
                        q.append(nei)
                        qed.add(nei)
            step += 1
                        
    def find_nei(self, node):
        alter = [
            (1, 2),
            (2, 1),
            (-1, 2),
            (2, -1),
            (1, -2),
            (-2, 1),
            (-1, -2),
            (-2, -1),
        ]
        return [
            tuple(node[i] + a[i] for i in range(2))
            for a in alter
        ]