Lengthy but self explanatory


#1

int matrix[500][500];
bool visited[500][500];
/the possible movements of knight/
int dx[] ={-2,2,-2,2,1,1,-1,-1};
int dy[] ={1,1,-1,-1,-2,2,-2,2};

bool isSafe(int i, int j,int A,int B){
if(i<0||j<0||i>=A||j>=B)
return false;
if(visited[i][j])
return false;
return true;
}

void bfs(int sx, int sy, int A, int B, int ex, int ey){

queue<pair<int,int>> q;
q.push({sx,sy});
visited[sx][sy]=true;
matrix[sx][sy]=0;

while(!q.empty()){
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    
    if(x == ex && y == ey)
        return;
    
    for(int i=0;i<8;i++){
        int newx = x+dx[i];
        int newy = y+dy[i];
        
        if(isSafe(newx,newy,A,B)){
            q.push({newx,newy});
            matrix[newx][newy] = matrix[x][y]+1;
            visited[newx][newy] = true;
        }
    }
}

}
int Solution::knight(int A, int B, int C, int D, int E, int F) {
memset(matrix, -1, sizeof matrix);
memset(visited, false, sizeof visited);
/converting the integers in 0 based system from 1 based system/
bfs(C-1,D-1,A,B,E-1,F-1);
return matrix[E-1][F-1];
}