InputThe input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.
OutputFor each test case, print one line saying "To get from xx to yy takes n knight moves.".
Sample Input
e2 e4 a1 b2 b2 c3 a1 h8 a1 h7 h8 a1 b1 c3 f6 f6
Sample Output
To get from e2 to e4 takes 2 knight moves. To get from a1 to b2 takes 4 knight moves. To get from b2 to c3 takes 2 knight moves. To get from a1 to h8 takes 6 knight moves. To get from a1 to h7 takes 5 knight moves. To get from h8 to a1 takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes 0 knight moves.
思路 ：骑士每次移动只能移动一个方格 其实就是一个日字（具体原因我也不知道）8个方向，，直接用BFS查找就可以了
#include<iostream> #include<queue> #include<string> #include<cstring> using namespace std; struct stu{ int a,b; }; char a,b; int aa,bb; int arr[10][10]; int arr1[10][10]; int arr2[10][10]; int ar[8][2]={{-2,-1},{-2,1},{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2}}; int bfs(int x1,int y1,int x2,int y2){ memset(arr1,0,sizeof(arr1)); queue<stu>que; que.push({x1,y1}); arr1[x1][y1]=1; arr2[x1][y1]=0; while(que.size()){ int x=que.front().a; int y=que.front().b; que.pop(); int dx,dy; for(int i=0;i<8;i++) { dx=x+ar[i][0]; dy=y+ar[i][1]; if(dx>=0&&dx<8&&dy>=0&&dy<8&&arr1[dx][dy]!=1){ arr1[dx][dy]=1; arr2[dx][dy]=arr2[x][y]+1; que.push({dx,dy}); if(dx==x2&&dy==y2){ return arr2[dx][dy]; } } } } return -1; } int main() { while(~scanf("%c%d %c%d",&a,&aa,&b,&bb)){ getchar(); for(int i=0;i<8;i++) { for(int j=0;j<8;j++) { arr[i][j]=1; } } int x1=a-‘a‘; // cout<<x1<<endl; int y1=aa-1; // cout<<y1<<endl; int x2=b-‘a‘; // cout<<x2<<endl; int y2=bb-1; // cout<<y2<<endl; arr[x1][aa-1]=0; arr[x2][bb-1]=0; if(x1==x2&&y1==y2) printf("To get from %c%d to %c%d takes 0 knight moves.\n",a,aa,b,bb); else { int y=bfs(x1,y1,x2,y2); printf("To get from %c%d to %c%d takes %d knight moves.\n",a,aa,b,bb,y); } } return 0; }
原文：https://www.cnblogs.com/Accepting/p/11241602.html