题目链接：http://poj.org/problem?id=2243 骑士遍历进阶版
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 #include <queue>
8 using namespace std;
9 int map[10][10];
10 char s1[3], s2[3];
11 const int dir[8][2] = {{2, 1}, {-2, 1}, {2, -1}, {-2, -1}, {1, 2}, {-1, 2}, {1, -2}, {-1, -2}};
12 struct data
13 {
14 int x, y;
15 }S, T;
16 queue<data> Q;
17 bool inMap(int x, int y)
18 {
19 return x >= 0 && x < 8 && y >= 0 && y < 8;
20 }
21 void init()
22 {
23 S.x = s1[0] - 'a';
24 S.y = s1[1] - '1';
25 T.x = s2[0] - 'a';
26 T.y = s2[1] - '1';
27 memset(map, -1, sizeof(map));
28 }
29 void bfs()
30 {
31 Q.push(S);
32 map[S.x][S.y] = 0;
33 data u, v;
34 while (!Q.empty())
35 {
36 u = Q.front();
37 Q.pop();
38 int x = u.x, y = u.y;
39 for (int i = 0; i < 8; i++)
40 {
41 int xx = x + dir[i][0];
42 int yy = y + dir[i][1];
43 if (!inMap(xx, yy)) continue;
44 if (map[xx][yy] == -1 || map[x][y] + 1 < map[xx][yy])
45 {
46 map[xx][yy] = map[x][y] + 1;
47 v.x = xx; v.y = yy;
48 Q.push(v);
49 }
50 }
51 }
52 }
53 int main()
54 {
55 while (~scanf("%s%s", s1, s2))
56 {
57 init();
58 bfs();
59 printf("To get from %s to %s takes %d knight moves.\n", s1, s2, map[T.x][T.y]);
60 }
61 return 0;
62 }
63
|