leetcode-graph

1197. Minimum Knight Moves.py

class Solution:
    """
    BFS
        It's a shortest problem. So we think about bfs.
        Starting bfs on knight. During the bfs, we keep track of step we moved, when we meet target(x,y), we reach our goal by return step.
        
    BFS+Pruning(Symmetric Properties)
        All solutions below are based on symmetry, meaning (x, y), (-x, y), (x, -y), (-x, -y) will have the same results.

        Instead of search whole boards with 8 direction when level by level bfs. So, we can do some pruning.
        
    Time Complexity: O(|x|*|y|) we at most have x*y cells
    
    Ref:
        1.https://www.youtube.com/watch?v=4pUElCFt4OA&ab_channel=RenZhang
        2.https://leetcode.com/problems/minimum-knight-moves/discuss/947138/Python-3-or-BFS-DFS-Math-or-Explanation
    """
    directions=[(1,2),(2,1),(1,-2),(2,-1),(-1,-2),(-2,-1),(-1,2),(-2,1)]
    def minKnightMoves(self, x: int, y: int) -> int:
        """
        BFS
        """
        q = collections.deque([(0,0,0)]) # (i,j,step)
        visited = set([(0,0)])
        while q:
            i, j, step = q.popleft()
            if (i, j) == (x, y):
                return step
            for direction in self.directions:
                next_i, next_j = i+direction[0], j+direction[1]
                if (next_i, next_j) not in visited:
                    q.append((next_i, next_j, step+1))
                    visited.add((next_i, next_j))
                    
    def minKnightMoves(self, x: int, y: int) -> int:
        """
        BFS + pruning
        """
        x, y = abs(x), abs(y)
        q = collections.deque([(0,0,0)]) # (i,j,step)
        visited = set([(0,0)])
        while q:
            i, j, step = q.popleft()
            if (i, j) == (x, y):
                return step
            for direction in self.directions:
                next_i, next_j = i+direction[0], j+direction[1]
                # next_i 比2還大會走太遠, 比-1還小會多花step走回來
                if (next_i, next_j) not in visited and -1<=next_i<= x+2 and -1<=next_j<= y+2:
                    q.append((next_i, next_j, step+1))
                    visited.add((next_i, next_j))