Zju1091 Knight Moves

1284: Zju1091 Knight Moves

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 86 Solved: 54
[Submit][Status][Web Board]

Description

在一个8*8的棋盘上，一只中国象棋中的马要从一个点跳到另一个点。问最少需要多少步。

Input

整个测试组由多组数据组成，请做到文件底结束。
对于每组数据，前两个坐标代表出发点，后两个代表结束点。注意坐标第一位为a至h中某个字母，第二位为1到8某个数字。

Output

对于每个测试请输出"To get from xx to yy takes n knight moves.".

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.

HINT

Source

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 int u[8]={-2,-2,-1,-1,1,1,2,2};
 5 int v[8]={-1,1,-2,2,-2,2,-1,1};
 6 int sx,sy,ex,ey;
 7 int g[9][9],x[90],y[90];
 8 
 9 void bfs()
10 {
11      int t,w,tx,ty,i;
12      memset(g,0,sizeof(g));
13      x[1]=sx; 
14      y[1]=sy;
15      g[sx][sy]=1;
16      t=0;
17      w=1;
18      do
19      {
20            t++;
21            for (i=0;i<8;i++)
22            {
23                tx=x[t]+u[i]; 
24                ty=y[t]+v[i];
25                if (tx<1 || tx>8 || ty<1 || ty>8 || g[tx][ty]!=0) 
26                continue;
27                g[tx][ty]=g[x[t]][y[t]]+1;
28                w++;
29                x[w]=tx; 
30                y[w]=ty;
31                if (tx==ex && ty==ey) 
32                return;
33            }
34      } while (t!=w);
35 }
36 
37 int main()
38 {
39     char c[4];
40     int i,ans;
41     while (cin>>c[0]>>c[1]>>c[2]>>c[3])
42     {
43           sx=c[0]-'a'+1; 
44           sy=c[1]-'0';
45           ex=c[2]-'a'+1; 
46           ey=c[3]-'0';
47           if (sx==ex && sy==ey) 
48           ans=0;
49           else
50           {
51               bfs(); 
52               ans=g[ex][ey]-1;
53           }
54           cout<<"To get from "<<c[0]<<c[1]<<" to "<<c[2]<<c[3]<<" takes "<<ans<<" knight moves.";
55           cout<<endl;
56     }
57     return 0 ;
58 }

knight