题意：给出8*8的棋盘，给出起点和终点，问最少走几步到达终点。
因为骑士的走法和马的走法是一样的，走日字形（四个象限的横竖的日字形）
另外字母转换成坐标的时候仔细一点（因为这个WA了两次---@_@）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define maxn 105 7 using namespace std; 8 struct node 9 { 10 int x,y; 11 int step; 12 } now,next,st,en; 13 queue<node>q; 14 char m,n; 15 int vis[maxn][maxn]; 16 int dir[8][2]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}}; 17 void bfs(int x,int y) 18 { 19 now.x=x;now.y=y;now.step=0; 20 while(!q.empty()) q.pop(); 21 q.push(now); 22 vis[x][y]=1; 23 while(!q.empty()) 24 { 25 now=q.front();q.pop(); 26 if(now.x==en.x&&now.y==en.y) 27 { 28 printf("To get from %c%d to %c%d takes %d knight moves. ",m,st.y,n,en.y,now.step); 29 return; 30 }; 31 for(int i=0;i<8;i++) 32 { 33 next.x=now.x+dir[i][0]; 34 next.y=now.y+dir[i][1]; 35 if(next.x<1||next.y>8||next.y<1||next.y>8) continue; 36 if(!vis[next.x][next.y]) 37 { 38 vis[next.x][next.y]=1; 39 next.step=now.step+1; 40 q.push(next); 41 if(next.x==en.x&&next.y==en.y) 42 { 43 printf("To get from %c%d to %c%d takes %d knight moves. ",m,st.y,n,en.y,next.step); 44 return; 45 } 46 } 47 } 48 } 49 } 50 int main() 51 { 52 while(cin>>m>>st.y>>n>>en.y) 53 { 54 memset(vis,0,sizeof(vis)); 55 st.x=m-'a'+1; 56 en.x=n-'a'+1; 57 bfs(st.x,st.y); 58 } 59 }