# 1197\. Minimum Knight Moves

"""BFS"""
class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        directions = [(1, 2), (2, 1), (-1, -2), (-2, -1), (-1, 2), (-2, 1), (1, -2), (2, -1)]
        def propagated(positions):
            next_positions = set()
            for x, y in positions:
                for dx, dy in directions:
                    if (x + dx, y + dy) not in seen:
                        next_positions.add((x + dx, y + dy))
                        seen.add((x + dx, y + dy))
            del positions  # must need this
            return next_positions
        i = 0
        positions = {(0, 0)}
        seen = {(0, 0)}
        while (x, y) not in positions:
            positions = propagated(positions)
            i += 1
        return i
            
"""BFS, two sources, bidirectional"""
class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        directions = [(1, 2), (2, 1), (-1, -2), (-2, -1), (-1, 2), (-2, 1), (1, -2), (2, -1)]
        
        def propagated(positions, seen):
            next_positions = set()
            for x, y in positions:
                for dx, dy in directions:
                    if (x + dx, y + dy) not in seen:
                        next_positions.add((x + dx, y + dy))
                        seen.add((x + dx, y + dy))
            del positions  # must need this
            return next_positions
        
        positions = {(0, 0)}
        seen = {(0, 0)}
        
        positions_target = {(x, y)}
        seen_target = {(x, y)}
    
        if (0, 0) == (x, y):
            return 0
        
        i = 0
        while True: 
            # It is wrong to do both propagated() then check,
            # Must check immediately after any propagated()
            positions = propagated(positions, seen)
            i += 1
            if len(positions & positions_target) > 0:
                return i 
            
            positions_target = propagated(positions_target, seen_target)
            i += 1
            if len(positions & positions_target) > 0:
                return i 
"""DFS"""
class Solution__:
    def minKnightMoves(self, x: int, y: int) -> int:
        pass

            

## math