Python 3 Solution using BFS O(A*B)


#1
def bfs(start,end,visited,board):

    count = 0
    queue = []
    queue.append(start)
    visited[start[0]][start[1]] = 1
    while queue:
        count +=1
        for _ in range(len(queue)):
            curr = queue[0]
            queue.pop(0)
            for val_i,val_j in [(2,-1),(-1,2),(-2,-1),(-1,-2),(-2,1),(1,-2),(2,1),(1,2)]:
                next_i,next_j = (curr[0]+val_i,curr[1]+val_j)
                if 0<=next_i<board[0] and 0<=next_j<board[1] and visited[next_i][next_j] == 0 :
                    if (next_i,next_j) == end:
                        return count
                    visited[next_i][next_j] = 1
                    queue.append((next_i,next_j))
    return -1     
        
class Solution:
    def knight(self, A, B, C, D, E, F):
        visited = [[0]*B for _ in range(A)]
        start = (C-1,D-1)
        end = (E-1,F-1)
        if start==end:
            return 0
        return bfs(start,end,visited,(A,B))