Code using BFS :


#1

vector<pair<int,int>> moves;
void fill_moves()
{
if(moves.size()>0)
return;
for(int i=-2;i<3;i++)
{
if(i == 0)
continue;
for(int j=-2;j<3;j++)
{
if(j == 0)
continue;
if(abs(j)+abs(i) != 3)
continue;
moves.push_back(make_pair(i,j));
//cout<<“i = “<<i<<” and j = “<<j<<”\n”;
}
}
}

int Solution::knight(int n, int m, int x1, int y1, int x2, int y2) {

fill_moves();
bool vis[n*m];
memset(vis, 0, sizeof(vis));
//cout<<"move size = "<<moves.size()<<"\n";

x1--;
y1--;
x2--;
y2--;

int s1 = x1*m+y1;
int d1 = x2*m+y2;


queue<int> q, q1;
q.push(s1), q1.push(0);
vis[s1] = 1;
int ans = INT_MAX;
while(!q.empty())
{
    int a1 = q.front(), a2 = q1.front();
    q.pop();
    q1.pop();
    
    //cout<<"arrive at "<<a1/m + 1<<" , "<<a1%m + 1<<" at "<<a2<<"\n";
    if(a1 == d1)
    {
        ans = min(ans, a2);
        continue;
    }
    
    for(int i=0;i<moves.size();i++)
    {
        int tx = a1/m + moves[i].first;
        int ty = a1%m + moves[i].second;
        if(tx<0 || tx>=n)
            continue;
        if(ty<0 || ty>=m)
            continue;
        int temp = m*moves[i].first + moves[i].second + a1;    
        if(vis[temp])
            continue;
        vis[temp] = 1;
        q.push(temp);
        q1.push(a2 + 1);
    }
}

if(ans == INT_MAX)
    ans = -1;

return ans;

}