# Lang: C++; Complexity[Time,Space]: [O(A*B), O(A*B)]

#1

Idea: You have to explore nodes one level at a time. Hence perform BFS from initial position till either you have reached destination or have visited all nodes which are reachable from that point.

``````inline bool isSafe(int x,int y, int A, int B) {
return (0<x && x<=A && 0<y && y<=B);
}
int Solution::knight(int A, int B, int C, int D, int E, int F) {
if(!isSafe(C,D,A,B)||!isSafe(E,F,A,B)) return -1;
if(C==E && D==F) return 0;

int count=0;
queue<pair<int,int>> q;
vector<vector<bool>> visited(A+1,vector<bool>(B+1,false));
vector<pair<int,int>> moves={{1,2},{2,1},{-1,2},{-2,1},{-1,-2},{-2,-1},{1,-2},{2,-1}};

q.push({C,D});
visited[C][D]=true;
while(!q.empty())
{
int knights=q.size();
while(knights--)
{
int x=q.front().first, y=q.front().second;
q.pop();
for(auto m: moves)
{
int x0=m.first, y0=m.second;
if(isSafe(x+x0,y+y0,A,B) && !visited[x+x0][y+y0])
{
if(x+x0==E && y+y0==F) return count+1;
visited[x+x0][y+y0]=true;
q.push({x+x0,y+y0});
}
}
}
count++;
}
return -1;
}
``````