BFS example

uva_knightMoves_439.cpp

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int jump[8][2]={{1,2},{-1,-2},{-1,2},{1,-2},{2,1},{-2,-1},{-2,1},{2,-1}};
int v[8][8];
int m[8][8];

int main()
{
    int i,j,x,y,sx,sy,dx,dy,jx,jy,r1,r2,moves,flag;
    char c1,c2;
    while(cin>>c1>>r1>>c2>>r2)
    {
        queue<int>q;
        sx = r1-1;
        sy = c1-97;
        dx=r2-1;
        dy=c2-97;
        flag=0;
        if(sx==dx && sy==dy)
        printf("To get from %c%d to %c%d takes 0 knight moves.\n",c1,r1,c2,r2);

        else
        {
        for(i=0;i<8;i++)
        for(j=0;j<8;j++)
        {
            v[i][j]=0;
            m[i][j]=0;
        }
        q.push(sx);
        q.push(sy);
        v[sx][sy]=1;
        m[sx][sy]=0;


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

            for(i=0;i<8;i++)
            {
                jx = x+jump[i][0];
                jy = y+jump[i][1];


                if(jx>=0 && jy>=0 && jx<8 && jy<8 && v[jx][jy]==0)
                {
                    q.push(jx);
                    q.push(jy);
                    v[jx][jy]=1;
                    m[jx][jy]=m[x][y]+1;
                    moves=m[jx][jy];
                    if(jx==dx && jy==dy)
                     {
                         flag=1;
                         break;
                     }
                }
            }
        if(flag)
        {
            printf("To get from %c%d to %c%d takes %d knight moves.\n",c1,r1,c2,r2,moves);
            break;
        }
        }
        }
      }
return 0;
}