Editorial for KNMOVE problem spoj - UCS - Unleash-Coding-Skills

Sunday, 4 March 2018

Editorial for KNMOVE problem spoj - UCS

  

SPOJ EDITORIAL FOR KNMOVE Problem:
 Problem link:
http://www.spoj.com/problems/KNMOVE/

Daniel is a chess player. At his free time, he usually plays chess with his family or his friends. But, sometimes they have their own activities, so Daniel can't play chess. He spends his time to learn about knight's move. He has 1,000 x 1,000 chessboard, numbered from 1 to 1,000. He wants to move his knight from (a,b) to (1,1) with minimum movement. Help Daniel to solve it.

Input

The input file consists of several lines.
The first line contains a single number t representing the number of question Daniel asked. [ 1<=t<=1,000 ]
The next t lines contains a and b representing knight's position on the chessboard. [ 1<= a,b <= 1,000 ]

Output

The output file should contains t lines.
The i-th line should contain one number – the minimum number of knight's movement.

Example

Input:
2
3 5
7 4

Output:
2
3

This question is a simple bfs approach but in this we need to precompute all things before since the time complexity here is 0.050 sec..In this first we follow approch that knight may be present at different locations and then we compute how many moves it take to reach (1,1) from that location


#include <iostream>
#include <queue>
#include <utility>
#include <cstdio>
using namespace std;
long long ans[1001][1001];
int e1,e2;
void  bfs(long long a,long long b)
{
    bool visit[1001][1001];
    for(int i=1;i<=1000;i++)
    {
        for(int j=1;j<=1000;j++)
        {
            ans[i][j]=-3200000;
        }
    }
    long long int i,j,k;
    pair<long long,long long>po;
    int ao[]={-2,-2,2,2,-1,-1,1,1};
    int bo[]={1,-1,1,-1,2,-2,2,-2};
    
    for(i=1;i<=1000;i++)
    {
        for(j=1;j<=1000;j++)
        {
        visit[i][j]=0;
        }
    }
    queue<pair<long long,long long> >q;
    visit[1][1]=1;
    ans[1][1]=0;
    q.push(make_pair(1,1));
    q.push(make_pair(-1,-1));
    pair<long long ,long long >io;
    io=make_pair(-1,-1);
    long long count=0;
 
    while(q.size()>1)
    {
po=q.front();
q.pop();
if(po==io)
{
 count++;
 q.push(io);
}
e1=po.first;
e2=po.second;
if(ans[e1][e2]<count)
{
ans[e1][e2]=count;

}

for(i=0;i<8;i++)
{
    int temx=e1+ao[i];
    int temy=e2+bo[i];
    if(temx>=1&&temx<=1000&&temy>=1&&temy<=10000&&(!visit[temx][temy]))
    {
        visit[temx][temy]=true;
        q.push(make_pair(temx,temy));
    }
}
    }
 

    
}
int main() {
long long int i,j,k,t,a,b;
scanf("%lld",&t);
bfs(1,1);
i=7,j=4;
int lo,li;
for(int kk=0;kk<t;kk++)
{
scanf("%d %d",&lo,&li);
printf("%lld\n",ans[lo][li]);
}
 return 0;
}


happy coding 🙂

No comments:

Post a comment