1197. Minimum Knight Moves

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        """ tc O(X*Y)  sc O(X*Y)
        main idea: limit the search on board onto quardrant.  take care of edge case where going to (1,1) from (0,0) takes 2 steps 
        """
        x,y = abs(x),abs(y)
        if x ==1 and y == 1:
            return 2
        dirs = [(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]
        q  = collections.deque()
        q.append((0,0))
        seen = set()
        seen.add((0,0))
        res = 0 
        while q :
            size = len(q)
            for i in range(size):
                xx,yy = q.popleft()
                if xx == x and yy == y :
                    return res 
                for dx, dy in dirs:
                    nx = xx + dx 
                    ny = yy + dy
                    if (nx,ny) not in seen and nx >= 0 and ny >= 0:
                        seen.add((nx,ny))
                        q.append((nx,ny))
            res += 1 
        return -1 

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        """ tc O(X*Y)  sc O(X*Y)
        main idea: move from target to origin as fast as possible + memo  + handling special cases 
        # (1) original (2) x + y == 2 
        """
        cache = {(1,1):2,(0,0):0,(2,0):2, (0,2):2}
        @lru_cache(None)
        def dfs(x,y):
            x,y = abs(x), abs(y)
            if (x,y) in cache: return cache[(x,y)]  
            return min(dfs(x-1,y-2),dfs(x-2,y-1)) + 1 
        return dfs(x,y)