Posted on 2008-05-03 16:27
superman 閱讀(477)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1091 C++ 00:00.08 844K */
2 #include <queue>
3 #include <iostream>
4
5 using namespace std;
6
7 struct rec { int x, y, cnt; };
8 struct { int x, y; } dir[8] = {
9 {-2, +1}, {-1, +2}, {+1, +2}, {+2, +1},
10 {+2, -1}, {+1, -2}, {-1, -2}, {-2, -1}
11 };
12
13 inline bool inside(const int x, const int y)
14 {
15 if(x >= 0 && x < 8 && y >= 0 && y < 8)
16 return true;
17 return false;
18 }
19
20 int BFS(int sx, int sy, int tx, int ty)
21 {
22 bool visited[8][8] = {false};
23
24 visited[sx][sy] = true;
25 rec cur = {sx, sy, 0};
26 queue <rec> q;
27 q.push(cur);
28
29 while(q.empty() == false)
30 {
31 cur = q.front(); q.pop();
32
33 if(cur.x == tx && cur.y == ty)
34 return cur.cnt;
35
36 for(int i = 0; i < 8; i++)
37 {
38 int x = cur.x + dir[i].x;
39 int y = cur.y + dir[i].y;
40
41 if(inside(x, y) && visited[x][y] == false)
42 {
43 visited[x][y] = true;
44 rec tmp = {x, y, cur.cnt + 1};
45 q.push(tmp);
46 }
47 }
48 }
49 }
50
51 int main()
52 {
53 char sx, sy, tx, ty;
54 while(cin >> sx >> sy >> tx >> ty)
55 {
56 sx -= 'a', sy = sy - '0' - 1;
57 tx -= 'a', ty = ty - '0' - 1;
58 printf("To get from %c%d to %c%d takes %d knight moves.\n",
59 sx + 'a', sy + 1, tx + 'a', ty + 1, BFS(sx, sy, tx, ty));
60 }
61
62 return 0;
63 }
64