最短路,搜索也可以
#include<stdio.h> #define inf 0x3fffffff int map[65][65]; int dir[4][2]={2,-1,2,1,1,2,-1,2}; int main() { int i,j,k,x,y; char s1[5],s2[5]; for(i=1;i<=64;i++) for(j=i+1;j<=64;j++) map[i][j]=map[j][i]=inf; for(i=0;i<8;i++)//建图 for(j=0;j<8;j++) { for(k=0;k<4;k++) { x=i+dir[k][0]; y=j+dir[k][1]; if(x>=0&&x<8&&y>=0&&y<8) { map[i*8+j+1][x*8+y+1]=1; map[x*8+y+1][i*8+j+1]=1; } } } for(k=1;k<=64;k++)//Floyd for(i=1;i<=64;i++) { if(i==k)continue; for(j=1;j<=64;j++) { if(j==i||j==k)continue; if(map[i][j]>map[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j]; } } while(scanf("%s%s",s1,s2)!=-1) { x=(s1[0]-'a')*8+s1[1]-'0'; y=(s2[0]-'a')*8+s2[1]-'0'; printf("To get from %s to %s takes %d knight moves.\n",s1,s2,map[x][y]); } return 0; }