这道读懂题意就很简单了，就宽搜就OK了。。
题意其实就是在一个8*8的国际象棋棋盘上下棋，骑士以马的形式跳（“日”字型，跟中国象棋一样，没拌点）
1 #include<iostream> 2 #include<string> 3 #include<queue> 4 #include<memory.h> 5 using namespace std; 6 7 struct node 8 { 9 int row; 10 int colum; 11 int m; 12 }; 13 int main() 14 { 15 int t; 16 cin>>t; 17 while(t--) 18 { 19 string a,b; 20 cin>>a>>b; 21 int colum1,row1,colum2,row2; 22 colum1=a[0]-'a'+1; 23 row1=a[1]-'0'; 24 colum2=b[0]-'a'+1; 25 row2=b[1]-'0'; 26 bool visit[9][9]; 27 queue<node> q; 28 node prime,over; 29 prime.row=row1; 30 prime.colum=colum1; 31 prime.m=0; 32 over.row=row2; 33 over.colum=colum2; 34 over.m=0; 35 q.push(prime); 36 memset(visit,false,sizeof(visit)); 37 visit[row1][colum1]=1; 38 while(!q.empty()) 39 { 40 node now=q.front(); 41 if(now.row==over.row&&now.colum==over.colum) 42 { 43 over.m=now.m; 44 break; 45 } 46 else 47 { 48 node w; 49 int i,j; 50 i=now.row-2; 51 j=now.colum+1; 52 if(visit[i][j]==0&&i>=1&&i<=8&&j>=1&&j<=8) 53 { 54 w.row=i; 55 w.colum=j; 56 w.m=now.m+1; 57 visit[i][j]=1; 58 q.push(w); 59 } 60 i=now.row-1; 61 j=now.colum+2; 62 if(visit[i][j]==0&&i>=1&&i<=8&&j>=1&&j<=8) 63 { 64 w.row=i; 65 w.colum=j; 66 w.m=now.m+1; 67 visit[i][j]=1; 68 q.push(w); 69 } 70 i=now.row+1; 71 j=now.colum+2; 72 if(visit[i][j]==0&&i>=1&&i<=8&&j>=1&&j<=8) 73 { 74 w.row=i; 75 w.colum=j; 76 w.m=now.m+1; 77 visit[i][j]=1; 78 q.push(w); 79 } 80 i=now.row+2; 81 j=now.colum+1; 82 if(visit[i][j]==0&&i>=1&&i<=8&&j>=1&&j<=8) 83 { 84 w.row=i; 85 w.colum=j; 86 w.m=now.m+1; 87 visit[i][j]=1; 88 q.push(w); 89 } 90 i=now.row+2; 91 j=now.colum-1; 92 if(visit[i][j]==0&&i>=1&&i<=8&&j>=1&&j<=8) 93 { 94 w.row=i; 95 w.colum=j; 96 w.m=now.m+1; 97 visit[i][j]=1; 98 q.push(w); 99 } 100 i=now.row+1; 101 j=now.colum-2; 102 if(visit[i][j]==0&&i>=1&&i<=8&&j>=1&&j<=8) 103 { 104 w.row=i; 105 w.colum=j; 106 w.m=now.m+1; 107 visit[i][j]=1; 108 q.push(w); 109 } 110 i=now.row-1; 111 j=now.colum-2; 112 if(visit[i][j]==0&&i>=1&&i<=8&&j>=1&&j<=8) 113 { 114 w.row=i; 115 w.colum=j; 116 w.m=now.m+1; 117 visit[i][j]=1; 118 q.push(w); 119 } 120 i=now.row-2; 121 j=now.colum-1; 122 if(visit[i][j]==0&&i>=1&&i<=8&&j>=1&&j<=8) 123 { 124 w.row=i; 125 w.colum=j; 126 w.m=now.m+1; 127 visit[i][j]=1; 128 q.push(w); 129 } 130 } 131 q.pop(); 132 } 133 cout<<"To get from "<<a<<" to "<<b<<" takes "<<over.m<<" knight moves."<<endl; 134 } 135 //system("pause"); 136 }