经典问题
走的方向确定，如dir[][]所示。
bfs 当搜到终点跳出
View Code
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 const int maxn = 10; 8 int mat[ maxn ][ maxn ]; 9 const int dir[8][2]={{2,1},{2,-1},{1,-2},{1,2},{-2,1},{-2,-1},{-1,-2},{-1,2}}; 10 struct node{ 11 int x,y,t; 12 }p,pp,start,e; 13 14 void bfs(){ 15 p.x=start.x,p.y=start.y,p.t=0; 16 memset( mat,0,sizeof( mat )); 17 queue<node>q; 18 q.push( p ); 19 mat[ p.x ][ p.y ]=1; 20 while( !q.empty() ){ 21 p=q.front(),q.pop(); 22 if( p.x==e.x && p.y==e.y ) return ; 23 for( int i=0;i<8;i++ ){ 24 pp.x=p.x+dir[ i ][ 0 ],pp.y=p.y+dir[ i ][ 1 ]; 25 if( pp.x<1||pp.x>8||pp.y<1||pp.y>8 ) continue; 26 if( mat[ pp.x ][ pp.y ]==1 ) continue; 27 mat[ pp.x ][ pp.y ]=1; 28 pp.t=p.t+1; 29 q.push( pp ); 30 } 31 } 32 return ; 33 } 34 35 int main(){ 36 char s1[ 4 ],s2[ 4 ]; 37 while( scanf("%s%s",s1,s2)!=EOF ){ 38 start.x=s1[ 0 ]-'a'+1,start.y=s1[ 1 ]-'0'; 39 e.x=s2[ 0 ]-'a'+1,e.y=s2[ 1 ]-'0'; 40 if( start.x==e.x && start.y==e.y ) 41 p.t=0; 42 else 43 bfs( ); 44 printf("To get from %s to %s takes %d knight moves.\n",s1,s2,p.t); 45 } 46 return 0; 47 }