| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 13974 | Accepted: 7797 |
Description
Input
Output
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.
Source
1 #include<cstdio> 2 #include<queue> 3 #include<algorithm> 4 #include<cstring> 5 6 using namespace std; 7 8 char s[5]; 9 bool v[9][9]; 10 int ex,ey,sx,sy,ans; 11 int dx[8]={2,1,-1,-2,-2,-1,1,2}; 12 int dy[8]={-1,-2,-2,-1,1,2,2,1};//八个方向 13 14 struct node 15 { 16 int x,y,step; 17 }cur,nxt; 18 19 queue<node>q; 20 21 void bfs() 22 { 23 if(ex==sx&&ey==sy) //特判起点等于终点 ，找到后进行输出就一定是最小的 24 { 25 printf("To get from %c%d to %c%d takes %d knight moves.\n",char(ex+‘a‘-1),ey,char(sx+‘a‘-1),sy,0); 26 return;//格式 27 } 28 while(!q.empty()) q.pop(); // 多组数据初始化 29 memset(v,0,sizeof(v)); // 同上 30 cur.x=ex,cur.y=ey; cur.step=0; //起点 31 v[ex][ey]=true; //不要漏了标记起点 32 q.push(cur); 33 while(!q.empty()) 34 { 35 cur=q.front(); 36 q.pop(); //不要漏了当前出队 37 //v[cur.x][cur.y]=false; 出队，清除标记，是否需要？不需要，为什么？ 38 for(int i=0;i<8;i++) //八方位搜索 39 { 40 int xx=cur.x+dx[i],yy=cur.y+dy[i]; 41 if(xx>0&&xx<=8&&yy>0&&yy<=8&&!v[xx][yy]) 42 { 43 if(xx==sx&&yy==sy) //找到了，第一个找到的一定就是最近的，why？ 44 { 45 printf("To get from %c%d to %c%d takes %d knight moves.\n",char(ex+‘a‘-1),ey,char(sx+‘a‘-1),sy,cur.step+1); 46 return ; 47 } 48 nxt.x=xx, nxt.y=yy; nxt.step=cur.step+1; 49 v[nxt.x][nxt.y]=true; 50 q.push(nxt); //扩展出的状态入队 51 } 52 } 53 } 54 } 55 56 int main() 57 { 58 while(scanf("%s",s)!=EOF) //注意输入，scanf读到空格 59 { 60 ex=s[0]-‘a‘+1; ey=s[1]-‘0‘; 61 scanf("%s",s); 62 sx=s[0]-‘a‘+1; sy=s[1]-‘0‘; 63 bfs(); 64 } 65 }
原文：http://www.cnblogs.com/zxqxwnngztxx/p/6814937.html