UVA-439 - ( Knight Moves ) ( Category : BFS )

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=380

Solution :

#include<bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

int visited[9][9];
int fx[]= {-2,-2,-1,1,2,-1,1,2};
int fy[]= {1,-1,2,2,1,-2,-2,-1};

int bfs(pii s,pii d)
{
    memset(visited,-1,sizeof(visited));

    int i,j,k,x,y;

    queue<pii>q;
    pii u,a;

    visited[s.first][s.second]=0;
    q.push(s);

    while(!q.empty())
    {
        u=q.front();
        q.pop();

        for(i=0; i<8; i++)
        {
            x=u.first+fx[i];
            y=u.second+fy[i];

            if(x>=1 and x<=8 and y>=1 and y<=8 and visited[x][y]==-1)
            {
                visited[x][y]=visited[u.first][u.second]+1;
                a.first=x;
                a.second=y;
                q.push(a);
            }
            if(a==d) break;
        }

    }

    return visited[d.first][d.second]-visited[s.first][s.second];
}

int main()
{

//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);

    char a,b,dummy;
    int c ,d,a1,b1;
    int v;

    while(scanf("%c%d%c%c%d",&a,&c,&dummy,&b,&d)==5)
    {
        getchar();

        a1=a-'a'+1;
        b1=b-'a'+1;

        pii s,ds;

        s.first=c;
        s.second=a1;
        ds.first=d;
        ds.second=b1;

        v= bfs(s,ds);

        printf("To get from %c%d to %c%d takes %d knight moves.\n",a,c,b,d,v);
    }



}