 |
| find out minimum steps a Knight will take to reach the target position. |
Output:
Print the minimum steps the Knight will take to reach the target position.
Print the minimum steps the Knight will take to reach the target position.
For Input:
5
3
1 3
1 2
2
2 1
2 1
3
3 3
2 1
4
2 2
1 3
5
1 3
1 5
Your Output is:
3
0
1
2
2
#include <bits/stdc++.h>
#include<tuple>
using namespace std;
int main(){
int t;
cin>>t;
while(t--)
{
int n,m,x,y,l,p=1,k=0;
cin>>n;
cin>>x>>y;
cin>>l>>m;
//create queue with tuple taking index and count
queue< tuple<int,int,int> > q;
//push origin index into queue
q.push(make_tuple(l,m,0));
int a[n+1][n+1];
a[l][m]=1;//origin is visited by assign 1
memset(a,0,sizeof(a));
//if not possible return 1 i.e p=1;
while(!q.empty())
{
// retrive the value from tuple which front of queue and pop
l=get<0>(q.front());
m=get<1>(q.front());
k=get<2>(q.front());
q.pop();
if(l==x&&m==y)
{ p=k;
break;
}
++k;
//there are possible 8 way for every position
// push every possible path with satisfied condition and mark as visited
if(l-1>0&&m+2<=n&&a[l-1][m+2]==0)
{
q.push(make_tuple(l-1,m+2,k));
a[l-1][m+2]=1;
}
if(l+1<=n&&m+2<=n&&a[l+1][m+2]==0)
{
q.push(make_tuple(l+1,m+2,k));
a[l+1][m+2]=1;
}
if(l-1>0&&m-2>0&&a[l-1][m-2]==0)
{
q.push(make_tuple(l-1,m-2,k));
a[l-1][m-2]=1;
}
if(l+1<=n&&m-2>0&&a[l+1][m-2]==0)
{
q.push(make_tuple(l+1,m-2,k));
a[l+1][m-2]=1;
}
if(l-2>0&&m+1<=n&&a[l-2][m+1]==0)
{
q.push(make_tuple(l-2,m+1,k));
a[l-2][m+1]=0;
}
if(l-2>0&&m-1>0&&a[l-2][m-1]==0)
{
q.push(make_tuple(l-2,m-1,k));
a[l-2][m-1]=1;
}
if(l+2<=n&&m+1<=n&&a[l+2][m+1]==0)
{
q.push(make_tuple(l+2,m+1,k));
a[l+2][m+1]=1;
}
if(l+2<=n&&m-1>0&&a[l+2][m-1]==0)
{
q.push(make_tuple(l+2,m-1,k));
a[l+2][m-1]=1;
}
}
cout<<p<<endl;
}
return 0;
}
