POJ 2243

#include <algorithm>
#include <iostream>
#include <utility>
#include <deque>
using namespace std;
typedef std::pair<int,int> move;
enum state {OUT=0, OK=1, VISITED=2, TARGET=-1};
typedef state board[12][12];
const int MOVES[8][2]={
   {-1,-2}, {-2,-1}, {-1,2}, {-2,1}, {1,-2}, {2,-1}, {1,2}, {2,1}
};
int go(board b,int x,int y){ //BFS
   if(b[x][y]==TARGET)
       return 0;
   deque<int> stepx[2];
   deque<int> stepy[2];
   stepx[0].push_back(x);
   stepy[0].push_back(y);
   int level=0;
   int l1=0,l2=1;
   while(true){
       ++level;
       if(stepx[l1].empty()) return -1;
       while(!stepx[l1].empty()){
           x=stepx[l1].front();
           stepx[l1].pop_front();
           y=stepy[l1].front();
           stepy[l1].pop_front();
           for(int i=0;i<8;++i){
               int tx=x+MOVES[i][0],ty=y+MOVES[i][1];
               if (b[tx][ty]==OUT) continue;
               if (b[tx][ty]==VISITED) continue;
               if (b[tx][ty]==TARGET) return level;
               b[tx][ty]=VISITED;
               stepx[l2].push_back(tx);
               stepy[l2].push_back(ty);
           }
       }
       l1^=l2^=l1^=l2;
   }
   return -1;
}

int main() {
   for(char f[3],t[3];cin>>f>>t;){
       const int xf=f[0]-'a',yf=f[1]-'1',xt=t[0]-'a',yt=t[1]-'1';
       board b={OUT};
       for(int i=2;i<10;++i)
           for(int j=2;j<10;++j)
               b[i][j]=OK;
       b[xf+2][yf+2]=VISITED;
       b[xt+2][yt+2]=TARGET;
       cout<<"To get from "<<f<<" to "<<t<<" takes "<<go(b,xf+2,yf+2)
           <<" knight moves."<<endl;
       //cout<<go(b,xf+2,yf+2)<<endl;
   }
   return 0;
}