杭电1372

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.

1 #include
        
          2 #include
         
           3 using namespace std; 4 int a[9][9]; 5 int x,y,m,n; 6 int c[8][2]={
      2,1, 2,-1, -2,1, -2,-1, 1,2, -1,2, 1,-2, -1,-2}; 7 struct node 8 { 9     int x,y,step;10 };11     12 int dfs()13 {14     int k;15     queue
          
           q;16     node cur,next;17     cur.x=x;18     cur.y=y;19     cur.step=0;20     q.push(cur);21     while(!q.empty())22     {23         cur=q.front();24         q.pop();25     26          27         for(k=0;k<8;k++)28         {29             next.x=cur.x+c[k][0];30             next.y=cur.y+c[k][1];31                 if(next.x==m&&next.y==n)32                     return cur.step+1;33             if(next.x<=0||next.y<=0||next.x>8||next.y>8||a[next.x][next.y]==1)34                 continue;35                  36                 next.step=cur.step+1;37                 q.push(next);38                 a[next.x][next.y]=1;39         40         }41     }42 }43 44 45 int main()46 {47     int b1,b2;48     char s1,s2;49     int t;50     while(scanf("%c",&s1)!=-1)51     {52         memset(a,0,sizeof(a));53         scanf("%d ",&b1);54         scanf("%c%d",&s2,&b2);55         getchar();56         x=s1-'a'+1;57         y=b1;58         m=s2-'a'+1;59         n=b2;60         a[x][y]=1;61         if(x==m&&y==n)62         {63             printf("To get from %c%d to %c%d takes %d knight moves.\n",s1,b1,s2,b2,0);64             continue;65         }66         else67             t=dfs();68     printf("To get from %c%d to %c%d takes %d knight moves.\n",s1,b1,s2,b2,t);69     }70     return 0;71 }