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)]
Python BFS solution :)
artemi
#1