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
                    adj=QueueNode(Point(row,col),curr.dist+1)
                    q.append(adj)
        
        return -1