#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct node 
{
int x, y;
bool step;
node() {
step = false;
}
};
bool operator==(const node& a, const node& b) {
return a.x == b.x && a.y == b.y;
}
const int MAXN = 1000;
int map[MAXN][MAXN];
queue<node> frontSearch;
queue<node> backSearch;
int fstep, bstep;
int di[8][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2},
{2, -1}, {2, 1}, {-2, 1}, {-2, -1}};
int main() {
int n, l;
scanf("%d", &n);
while(n --) {
while(!frontSearch.empty())
frontSearch.pop();
while(!backSearch.empty())
backSearch.pop();
memset(map, 0, sizeof map);
node start, finish, current, temp;
scanf("%d", &l);
scanf("%d%d", &start.x, &start.y);
scanf("%d%d", &finish.x, &finish.y);
if(start == finish) {
printf("0\n");
continue;
}
fstep = 0, bstep = 0;
start.step = true, finish.step = true;
map[start.x][start.y] = 1;
map[finish.x][finish.y] = 2;
frontSearch.push(start);
backSearch.push(finish);
while(!frontSearch.empty() || !backSearch.empty()) {
if(!frontSearch.empty()) {
do{
current = frontSearch.front();
frontSearch.pop();
int xx, yy, i;
for(i = 0 ; i < 8 ; ++i) {
xx = current.x + di[i][0], yy = current.y + di[i][1];
if(xx < 0 || xx >= l || yy < 0 || yy >= l)
continue;
if(map[xx][yy] == 2)
goto loop1;
if(!map[xx][yy]) {
map[xx][yy] = 1;
temp.x = xx, temp.y = yy;
frontSearch.push(temp);
}
}
}while(!current.step);
fstep ++;
current = frontSearch.front();
frontSearch.pop();
current.step = true;
frontSearch.push(current);
}
if(!backSearch.empty()) {
do{
current = backSearch.front();
backSearch.pop();
int xx, yy, i;
for(i = 0 ; i < 8 ; ++i) {
xx = current.x + di[i][0], yy = current.y + di[i][1];
if(xx < 0 || xx >= l || yy < 0 || yy >= l)
continue;
if(map[xx][yy] == 1)
goto loop2;
if(!map[xx][yy]) {
map[xx][yy] = 2;
temp.x = xx, temp.y = yy;
backSearch.push(temp);
}
}
}while(!current.step);
fstep ++;
current = backSearch.front();
backSearch.pop();
current.step = true;
backSearch.push(current);
}
}
loop1:
loop2:
printf("%d\n", fstep + bstep + 1);
}
return 0;
}
posted on 2010-01-09 23:57
shmily 阅读(126)
评论(0) 编辑 收藏 引用