# Simple BFS using Python ( O(M*N) Space Complexity )

#1

from collections import deque
class Point:
def init(self,x:int,y:int):
self.x=x
self.y=y
class QueueNode:
def init(self,pt:Point,dist:int):
self.pt=pt
self.dist=dist

class Solution:
# @param A : integer
# @param B : integer
# @param C : integer
# @param D : integer
# @param E : integer
# @param F : integer
# @return an integer

``````def knight(self, A, B, C, D, E, F):

def isValid(row,col):
if row<0 or col<0 or row>=A or col>=B:
return False
return True

dp=[[0 for j in range(B)] for i in range(A)]

#visited=[[False for j in range(B)] for i in range(A)]

movesX=[2, 1, -1, -2, -2, -1, 1, 2]
movesY = [1, 2, 2, 1, -1, -2, -2, -1]

if dp[C-1][D-1]!=0 or dp[E-1][F-1]!=0:
return -1

dp[C-1][D-1]=1

q=deque()
s=QueueNode(Point(C-1,D-1),0)
q.append(s)

while q:

curr=q.popleft()
pt=curr.pt

if pt.x==E-1 and pt.y==F-1:
return curr.dist

for i in range(8):
row=pt.x+movesX[i]
col=pt.y+movesY[i]

if isValid(row,col) and dp[row][col]==0:

dp[row][col]=1