1074 - 马的移动
小明很喜欢下国际象棋，一天，他拿着国际象棋中的“马”时突然想到一个问题：
给定两个棋盘上的方格a和b，马从a跳到b最少需要多少步？
现请你编程解决这个问题。
提示：国际象棋棋盘为8格*8格，马的走子规则为，每步棋先横走或直走一格，然后再往外斜走一格。
Input
输入包含多组测试数据。每组输入由两个方格组成，每个方格包含一个小写字母（a~h），表示棋盘的列号，和一个整数（1~8），表示棋盘的行号。
Output
对于每组输入，输出一行“To get from xx to yy takes n knight moves.”。
Examples
Input
e2 e4 a1 b2 b2 c3 a1 h8 a1 h7 h8 a1 b1 c3 f6 f6
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.
Solution C
#include <stdio.h> #include <string.h> #include <stdlib.h> main() { int time,times[8][8]={0, 3, 2, 3, 2, 3, 4, 5, 3, 2, 1, 2, 3, 4, 3, 4, 2, 1, 4, 3, 2, 3, 4, 5, 3, 2, 3, 2, 3, 4, 3, 4, 2, 3, 2, 3, 4, 3, 4, 5, 3, 4, 3, 4, 3, 4, 5, 4, 4, 3, 4, 3, 4, 5, 4, 5, 5, 4, 5, 4, 5, 4, 5, 6}; char x[3],y[3]; while(scanf("%s%s",&x,&y)!=EOF) { if((strcmp(x,"a1\0")==0 && strcmp(y,"b2\0")==0)||(strcmp(x,"a8\0")==0 && strcmp(y,"b7\0")==0)||(strcmp(x,"h1\0")==0 && strcmp(y,"g2\0")==0)||(strcmp(x,"h8\0")==0 && strcmp(y,"g7\0")==0)||(strcmp(x,"b2\0")==0 && strcmp(y,"a1\0")==0)||(strcmp(x,"b7\0")==0 && strcmp(y,"a8\0")==0)||(strcmp(x,"g2\0")==0 && strcmp(y,"h1\0")==0)||(strcmp(x,"g7\0")==0 && strcmp(y,"h8\0")==0)) { time=4; } else { time=times[abs(x[0]-y[0])][abs(x[1]-y[1])]; } printf("To get from %s to %s takes %d knight moves.\n",x,y,time); } return 0; }
Solution C++
#include<stdio.h> #include<string.h> #include<queue> using namespace std; struct K { int x,y,step; }start,end; char s[3],e[3]; int f[][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}},v[8][8]; int bfs() { memset(v,0,sizeof(v)); struct K head,tail; queue<struct K> q; q.push(start); start.step=0; v[start.x][start.y]=1; while(!q.empty()) { head=q.front(); q.pop(); for(int i=0;i<8;i++) { tail.x=head.x+f[i][0]; tail.y=head.y+f[i][1]; tail.step=head.step+1; if(!v[tail.x][tail.y]&&tail.x>=0&&tail.x<8&&tail.y>=0&&tail.y<8) { if(tail.x==end.x&&tail.y==end.y) return tail.step; v[tail.x][tail.y]=1; q.push(tail); } } } } int main() { while(scanf("%s%s",s,e)!=EOF) { start.x=s[1]-'0'-1; start.y=s[0]-'a'; end.x=e[1]-'0'-1; end.y=e[0]-'a'; if(!strcmp(s,e)) printf("To get from %s to %s takes 0 knight moves.\n",s,e); else printf("To get from %s to %s takes %d knight moves.\n",s,e,bfs()); } return 0; }