【HDOJ-1372】Knight Moves

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 using namespace std;
 5 int movex[8][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
 6 int mark[10][10];
 7 int step[10][10];
 8 int bfs(int a,int b,int c,int d);
 9 int main()
10 {
11     int a0,b0,an,bn;
12     char temp1,temp2;
13     while(scanf("%c%d %c%d",&temp1,&b0,&temp2,&bn)!=EOF)
14     {
15         getchar();
16         memset(mark,0,sizeof(mark));
17         memset(step,0,sizeof(step));
18         a0=temp1-‘a‘+1;
19         an=temp2-‘a‘+1;
20         if(temp1==temp2&&b0==bn)
21         {
22             printf("To get from %c%d to %c%d takes 0 knight moves.\n",temp1,b0,temp2,bn);
23             continue;
24         }
25         int ans=bfs(a0,b0,an,bn);
26         printf("To get from %c%d to %c%d takes %d knight moves.\n",temp1,b0,temp2,bn,ans);
27     }
28     return 0;
29 }
30 
31 int bfs(int a,int b,int c,int d)
32 {
33     queue<int> qx;
34     queue<int> qy;
35     qx.push(a);
36     qy.push(b);
37     mark[a][b]=1;
38     while(!qx.empty()&&!qy.empty())
39     {
40         int i;
41         for(i=0;i<8;i++)
42         {
43             int nx=qx.front()+movex[i][0];
44             int ny=qy.front()+movex[i][1];
45             if(nx>=1&&nx<=8&&ny>=1&&ny<=8&&!mark[nx][ny])
46             {
47                 mark[nx][ny]=1;
48                 step[nx][ny]=step[qx.front()][qy.front()]+1;
49                 qx.push(nx);
50                 qy.push(ny);
51                 if(nx==c&&ny==d)
52                     return step[nx][ny];
53             }
54         }
55         qx.pop();
56         qy.pop();
57     }
58 }