HDU 1372 Knight Moves 简单BFS

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1372

大体意思是给你一个8*8的棋盘，然后给你两个字母与数字的组合，字母代表的是行，数字代表咧，让你找出从第一个组合的位置到第二个组合的位置，至少要走多少步。

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 struct node
 4 {
 5     int x,y,step;
 6 }q[100005];
 7 int map[15][15];
 8 int pro[15][15];
 9 int to[8][2] = {{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
10 int f,r,step;
11 int main()
12 {
13     char s1[10],s2[10];
14     int x1,x2,y1,y2,leap,i;
15     while(scanf("%s %s",s1,s2)!=EOF)
16     {
17         x1 = s1[0] - 'a';
18         x2 = s2[0] - 'a';
19         y1 = s1[1] - '1';
20         y2 = s2[1] - '1';
21         memset(map,0,sizeof(map));
22         memset(pro,0,sizeof(pro));
23         f = r = step = 0;
24         q[r].x = x1;
25         q[r].y = y1;
26         r++;
27         leap = 1;
28         map[x1][y1] = 1;
29         while(f < r)
30         {
31             struct node v;
32             v = q[f];
33             step = q[f].step;
34             f++;
35             for(i = 0;i < 8;i++)
36             {
37                 int tx,ty;
38                 tx = v.x+to[i][0];
39                 ty = v.y+to[i][1];
40                 if(tx >= 0&&tx < 8&&ty >= 0&&ty < 8 && !map[tx][ty])
41                 {
42                     q[r].x = tx;
43                     q[r].y = ty;
44                     q[r].step = step+1;
45                     if(tx == x2 && ty == y2)
46                     {
47                         leap = 0;
48                         break;
49                     }
50                     map[tx][ty] = 1;
51                     r++;
52                 }
53             }
54             if(!leap)
55             break;
56         }
57         if(!leap)
58         printf("To get from %s to %s takes %d knight moves.\n",s1,s2,q[r].step);
59         else
60         printf("To get from %s to %s takes 0 knight moves.\n",s1,s2);
61     }
62     return 0;
63 }