1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 int IsVis[9][9];//记录位置是否被访问 7 int StaX,StaY,EndX,EndY; 8 char Start[3],End[3]; //起始及结束位置 9 typedef struct node10 {11     int x,y,MoveNum;12 }knight;13 int Move[8][2]={-1,2, -2,1, 2,1, 1,-2, 1,2, 2,-1, -1,-2, -2,-1};//骑士的移动方位14 void Bfs(int x,int y);15 16 int main(){17     //freopen("D:\\t.txt","r",stdin);18     while(cin>>Start>>End){19         StaX = Start[0] - 'a' + 1;20         StaY = Start[1] - '0';21         EndX = End[0] - 'a' + 1;22         EndY = End[1] - '0';//对输入的棋子的位置进行处理23         Bfs(StaX,StaY);24     }25     return 0;26 }27 void Bfs(int x,int y){28     knight m,n;29     queue
        
          Que;30 31     m.x = x;32     m.y = y;33     m.MoveNum = 0;34     memset(IsVis,0,sizeof(IsVis));//每一回合棋盘初始化35     IsVis[m.x][m.y] = 1;36     Que.push(m);37     while(!Que.empty()){38         m = Que.front();39         Que.pop();40         if(m.x == EndX&&m.y == EndY){41             cout<<"To get from "<
         
          <
          
           <<" to "<
           
            <<" takes "<
            
             <<" knight moves."<
             
              < 8;i++){45 if((m.x + Move[i][0] > 0) && (m.x + Move[i][0] < 9) && (m.y + Move[i][1] > 0) && (m.y + Move[i][1] < 9)46 && !IsVis[m.x + Move[i][0]][m.y + Move[i][1]]){ //判断移动是否超范围及是否被访问47 n.x = m.x + Move[i][0];48 n.y = m.y + Move[i][1];49 n.MoveNum = m.MoveNum + 1;50 Que.push(n);51 }52 }53 }54 55 }
             
            
           
          
         
        
       
      
     

 

题目说的是骑士从一个位置移动到另一个位置所需的步数，国际象棋里骑士移动和中国象棋里的马类似，都是“日”形。

 题目用bfs求解，要运用到队列，使得骑士走的步数不断更新。以便在bfs过程中，统计的移动步数是最短的。