简单的对于bfs的运用，但是还是写的太慢了写了TMD的1H，主要是不熟悉，以后慢慢熟悉就好了，模型基本已经能建立了，主要出现bug是在方向数组的运用上面，一定要记得是从0开始的，而不是从1开始的，导致错误。
#include<cstdio> #include<cstdlib> #include<iostream> using namespace std; /*bfs*/ //方向数组 int nextx[8][2]={ {-1,-2}, {-2,-1}, {1,2}, {2,1}, {1,-2}, {2,-1}, {-1,2}, {-2,1} }; /* 1 0 3 0 5 6 7 8 9 0 2 3 4 0 6 7 8 9 1 2 0 4 5 6 7 8 9 0 2 3 4 0 6 7 8 9 1 0 3 0 5 6 7 8 9 1 2 3 4 5 6 7 8 9 */ struct que { int x;//当前的A； int y;//当前的B； int step;//走过的步数 }; int main() { int i;//循环变量 int y1,y2; int x1,x2; int nowX,nowY; char ch[10]; int head=1; int tail=1; struct que ques[100]; while (gets(ch) != NULL) { //将输入的数转换成对应数字 x1 = ch[0]-'a'+1; y1 = ch[1]-'0'; x2 = ch[3]-'a'+1; y2 = ch[4]-'0'; //初始化地图，用于记录走过的点 int maps[10][10]={0}; head=1; tail=1; maps[x1][y1] = 1;//记录初始点 ques[head].x = x1; ques[head].y = y1; ques[head].step = 0; tail++; nowX=x1; nowY=y1; if(nowX == x2 && nowY == y2) { goto f1; } while (head<tail) { for (i = 0; i < 8; i++) { nowX = ques[head].x + nextx[i][0]; nowY = ques[head].y + nextx[i][1]; if(nowX<=0 || nowX>8 || nowY<=0 || nowY>8) continue; if(maps[nowX][nowY] == 0) { maps[nowX][nowY] = 1; ques[tail].x = nowX; ques[tail].y = nowY; ques[tail].step = ques[head].step + 1; tail++; } if(nowX == x2 && nowY == y2) { goto f1; } } head++; } f1:printf("To get from %c%d to %c%d takes %d knight moves. ",ch[0],y1,ch[3],y2,ques[tail-1].step); } return 0; } /* 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. */