Posted on 2008-06-21 14:37
superman 阅读(796)
评论(0) 编辑 收藏 引用 所属分类:
POJ
1 /* Accepted 2488K 688MS G++ 3131B */
2 #include <queue>
3 #include <iostream>
4
5 using namespace std;
6
7 struct point { int x, y; } ;
8
9 point dir[8] = {
10 {-2, +1}, {-1, +2}, {+1, +2}, {+2, +1},
11 {+2, -1}, {+1, -2}, {-1, -2}, {-2, -1}
12 };
13
14 int n, a[300][300], b[300][300];
15
16 inline bool inside(const int x, const int y)
17 {
18 if(x >= 0 && x < n && y >= 0 && y < n)
19 return true;
20 return false;
21 }
22
23 int bfs(int sx, int sy, int tx, int ty)
24 {
25 for(int i = 0; i < n; i++)
26 for(int j = 0; j < n; j++)
27 a[i][j] = b[i][j] = -1;
28
29 a[sx][sy] = b[tx][ty] = 0;
30
31 queue <point> l, r;
32 point sp = { sx, sy };
33 point tp = { tx, ty };
34 l.push(sp); r.push(tp);
35
36 point cp;
37 while(l.empty() == false || r.empty() == false)
38 {
39 if(l.empty() == false)
40 {
41 cp = l.front(); l.pop();
42 for(int i = 0; i < 8; i++)
43 {
44 int x = cp.x + dir[i].x;
45 int y = cp.y + dir[i].y;
46 if(inside(x, y))
47 {
48 if(a[x][y] == -1)
49 {
50 a[x][y] = a[cp.x][cp.y] + 1;
51 point np = { x, y };
52 l.push(np);
53 }
54 if(b[x][y] != -1)
55 return a[x][y] + b[x][y];
56 }
57 }
58 }
59 if(r.empty() == false)
60 {
61 cp = r.front(); r.pop();
62 for(int i = 0; i < 8; i++)
63 {
64 int x = cp.x + dir[i].x;
65 int y = cp.y + dir[i].y;
66 if(inside(x, y))
67 {
68 if(b[x][y] == -1)
69 {
70 b[x][y] = b[cp.x][cp.y] + 1;
71 point np = { x, y };
72 r.push(np);
73 }
74 if(a[x][y] != -1)
75 return a[x][y] + b[x][y];
76 }
77 }
78 }
79 }
80 }
81
82 int main()
83 {
84 cin >> n;
85 while(cin >> n)
86 {
87 int sx, sy, tx, ty;
88 cin >> sx >> sy >> tx >> ty;
89
90 if(sx == tx && sy == ty)
91 cout << 0 << endl;
92 else
93 cout << bfs(sx, sy, tx, ty) << endl;
94 }
95
96 return 0;
97 }
98