#include <stdio.h>
#include <string.h>
typedef struct{
int level;
int row;
int col;
}position;
position queue[90000];
int chess[300][300];
int x[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int y[8] = {2, 1, -1, -2, -2, -1, 1, 2};
static void input_init(position *begin, position *end, int *wide);
static void bfs(position *begin, position *end, int *wide);
int main(int argc, char **argv)
{
int tests;
int wide;
position begin, end;
scanf("%d", &tests);
getchar();
while(tests--){
input_init(&begin, &end, &wide);
bfs(&begin, &end, &wide);
}
return 0;
}
static void input_init(position *begin, position *end, int *wide)
{
scanf("%d", wide);
getchar();
scanf("%d %d", &(begin->row), &(begin->col));
getchar();
scanf("%d %d", &(end->row), &(end->col));
getchar();
return;
}
static void bfs(position *begin, position *end, int *wide)
{
int templevel = 0, head = 0, tail = 0, flag = 0, d;
position temp, newtemp;
memset(chess, 0, sizeof(chess));
memset(queue, 0, sizeof(queue));
if((begin->row == end->row) && (begin->col == end->col)){
printf("%d\n", flag);
return;
}
chess[begin->row][begin->col] = 1;
begin->level = 0;
queue[tail++] = *begin;
while(head <= tail){
temp = queue[head++];
templevel = temp.level + 1;
for(d = 0; d < 8; d++){
newtemp.row = temp.row + x[d];
newtemp.col = temp.col + y[d];
newtemp.level = templevel;
if((newtemp.row == end->row) && (newtemp.col == end->col)){
printf("%d\n", newtemp.level);
return;
}
if((newtemp.row >= 0) && (newtemp.row < *wide) && \
(newtemp.col >= 0) && (newtemp.col < *wide) \
&& (chess[newtemp.row][newtemp.col] == 0)){
queue[tail++] = newtemp;
chess[newtemp.row][newtemp.col] = 1;
}
}
}
return;
}
|