hdu 1372 骑士从起点走到终点的步数 (BFS)

给出起点和终点求骑士从起点走到终点所需要的步数

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 <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <queue>
 5 using namespace std;
 6 
 7 
 8 int map[15][15];
 9 int sx, sy;
10 int ex, ey;
11 bool flag;
12 char s1[5] , s2[5] ;
13 
14 int dx[] = {-2,-1,1,2,-2,-1,1,2} ;
15 int dy[] = {1,2,2,1,-1,-2,-2,-1} ;
16 
17 struct node
18 {
19     int x , y , step ;
20 };
21 
22 int bfs()
23 {
24     queue<node> q ;
25     int i , fx ,fy ;
26     node now , t ;
27     now.x = sx ;
28     now.y = sy ;
29     now.step = 0 ;
30     q.push(now) ;
31     memset(map , 0 , sizeof(map)) ;
32     map[sx][sy] = 1 ;
33     while(!q.empty())
34     {
35         now = q.front() ;
36         q.pop() ;
37         for (i = 0 ; i < 8 ; i++)
38         {
39             fx = now.x + dx[i] ;
40             fy = now.y + dy[i] ;
41             if (fx<0 || fy<0 || fx>= 8 || fy>= 8 || map[fx][fy] == 1)
42                 continue ;
43             if (fx == ex && fy == ey)
44             {
45                 return now.step+1 ;
46             }
47             t.x = fx ;
48             t.y = fy ;
49             t.step = now.step+1 ;
50             q.push(t) ;
51             map[fx][fy] = 1 ;
52         }
53     }
54     return 0 ;
55 }
56 
57 
58 
59 int main()
60 {
61     //freopen("in.txt","r",stdin) ;
62     while (scanf("%s %s" , &s1 , &s2) !=EOF)
63     {
64         sx = s1[0] - 'a' ;
65         sy = s1[1] - '1' ;
66         ex = s2[0] - 'a' ;
67         ey = s2[1] - '1' ;
68         printf("To get from %s to %s takes %d knight moves.
",s1,s2,bfs()) ;
69     }
70 
71 
72 
73     return 0 ;
74 }

View Code