題目鏈接：http://poj.org/problem?id=1915 又是喜聞樂見的騎士遍歷，聽說雙向廣搜可以提升效率，但是雙向廣搜不會啊親。。   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[310][310], n;
10 const int dir[8][2] = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
11 struct nod{
12 int x, y;
13 }S, T;
14 queue<nod> Q;
15 void init(){
16 for (int i = 0; i < n; i++)
17 for (int j = 0; j < n; j++)
18 map[i][j] = -1;
19 }
20 bool inMap(int x, int y){
21 return x >= 0 && x < n && y >= 0 && y < n;
22 }
23 void bfs(){
24 map[S.x][S.y] = 0;
25 Q.push(S);
26 while (!Q.empty()){
27 nod u = Q.front();
28 Q.pop();
29 int x = u.x, y = u.y;
30 for (int i = 0; i < 8; i++){
31 int xx = x + dir[i][0];
32 int yy = y + dir[i][1];
33 if (!inMap(xx, yy)) continue;
34 if (map[xx][yy] == -1 || map[xx][yy] > map[x][y] + 1){
35 map[xx][yy] = map[x][y] + 1;
36 nod v; v.x = xx; v.y = yy;
37 Q.push(v);
38 }
39 }
40 }
41 }
42 int main(){
43 int t;
44 scanf("%d", &t);
45 while (t--){
46 scanf("%d", &n);
47 scanf("%d%d%d%d", &S.x, &S.y, &T.x, &T.y);
48 init();
49 bfs();
50 printf("%d\n", map[T.x][T.y]);
51 }
52 return 0;
53
|