document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #include <iostream>
  2. #include <string>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. struct Point{
  7. public:
  8.     int x;
  9.     int y;
  10.     int step;
  11.    
  12.     Point(int setx,int sety,int step);
  13.     bool CheckBound(int x, int y);
  14.     bool ReachEnd(int endX, int endY);
  15. };
  16.  
  17. Point::Point( int setx , int sety, int step): x(setx), y(sety), step(step) {  //?? what about label[8][8]?
  18.     //label[setx][sety]=1;
  19. }
  20.  
  21. bool Point::CheckBound(int x,int y){
  22.     return (x>=0 && x<8 && y>=0 && y<8) ? true:false;
  23. }
  24.  
  25. //void Point::Expand(int x,int y,int[8][8] label){}
  26.  
  27. bool Point::ReachEnd(int endX, int endY){
  28.     return (x==endX && y==endY)? true:false;
  29. }
  30.  
  31.  
  32. int main() {
  33.    
  34.     string startStr,endStr;
  35.     while(cin>>startStr>>endStr){
  36.         int startX,startY;
  37.         int endX,endY;
  38.  
  39.         startX = startStr[0]-\'a\';
  40.         startY = startStr[1]-\'1\';
  41.         endX = endStr[0]-\'a\';
  42.         endY = endStr[1]-\'1\';
  43.  
  44.         int label[8][8]={0};
  45.         Point start(startX,startY,0);
  46.         Point end(endX,endY,0);
  47.         Point temp(0,0,0);
  48.  
  49.         if( start.ReachEnd(endX,endY) ){
  50.             cout<<"To get from "<<startStr<<" to "<<endStr<<" takes 0 knight moves."<<endl;
  51.             continue;
  52.         }
  53.  
  54.         queue<Point> BFS;
  55.         const int knight[8][2]={{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}};
  56.        
  57.         BFS.push(start);
  58.         bool find = false;
  59.  
  60.         while(!find){
  61.             //initail
  62.             temp = BFS.front();
  63.             BFS.pop();
  64.             label[temp.x][temp.y]=1;
  65.             //found end
  66.             if(temp.ReachEnd(end.x,end.y)){
  67.                     cout<<"To get from "<<startStr<<" to "<<endStr<<" takes "<<temp.step<<" knight moves."<<endl;
  68.                     find = true;
  69.                     break;
  70.             }
  71.             //expand
  72.             for(int i=0;i<8;i++){
  73.                 int expandedX = temp.x+knight[i][0];
  74.                 int expandedY = temp.y+knight[i][1];
  75.                 if ( temp.CheckBound(expandedX,expandedY) && label[expandedX][expandedY]==0 )
  76.                 {
  77.                     label[expandedX][expandedY] = 1;
  78.                     Point expandedPoint(expandedX,expandedY,temp.step+1);
  79.                     BFS.push(expandedPoint);
  80.                 }
  81.             }
  82.         }  
  83.     }
  84.  
  85.     return 0;
  86. }
');