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;
``````

}