Python BFS solution :)


#1
import collections, sys
class Solution:
    def returnSteps(self, X, Y, KX, KY, D, L, TX, TY):
        if D[(KX, KY)] > L:
            D[(KX, KY)] = L
            if KX == TX and KY == TY:
                return set()
            return set(a for a in [(KX+2, KY+1),(KX+2, KY-1),
                                (KX-2, KY+1),(KX-2, KY-1),
                                (KX+1, KY+2),(KX+1, KY-2),
                                (KX-1, KY+2),(KX-1, KY-2)]
                                if a[0] >= 0 and a[1] >= 0 and a[0] < X and a[1] < Y)
        else:
            return set()

    def knight(self, X, Y, KX, KY, TX, TY):
        TX, TY = TX-1, TY-1
        Q = set()
        Q.add((KX-1, KY-1))
        D = collections.defaultdict(lambda : sys.maxsize)
        L = 0
        while (Q):
            T = set()
            for a in Q:
                P = self.returnSteps(X, Y, a[0], a[1], D, L, TX, TY)
                T |= P
            L += 1
            Q = T
        if D[(TX, TY)] == sys.maxsize:
            return -1
        return D[(TX, TY)]