拿这个经典题目开刀...........可是双向时间优势在这题上的效果不太明显
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 333
#define INF 0x7FFFFFFF
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std; int num1[MAX][MAX],num2[MAX][MAX];
int map[MAX][MAX];
int dirx[8] = {2, 2, -2, -2, 1, 1, -1, -1};
int diry[8] = {-1, 1, -1, 1, -2, 2, -2, 2}; struct node
{
int x,y;
}start,end;
int n;
void init()
{
memset(map,0,sizeof(map));
memset(num1,-1,sizeof(num1));
memset(num2,-1,sizeof(num2));
} bool inside(int x,int y)
{
if(x<0 || x>=n || y<0 || y>=n)
return false;
return true;
}
void dbfs()
{
queue<node>p,q;
p.push(start);
num1[start.x][start.y] = 0;
q.push(end);
num2[end.x][end.y] = 0;
while(!p.empty() && !q.empty())
{
node t,tt;
int size = p.size();
while(size--)
{
t = p.front();
p.pop();
if(inside(t.x,t.y) && num2[t.x][t.y] != -1)
{
printf("%d\n",num1[t.x][t.y] + num2[t.x][t.y]);
return ;
}
for(int i=0; i<8; i++)
{
tt.x = t.x + dirx[i];
tt.y = t.y + diry[i];
if(inside(tt.x,tt.y) && num2[tt.x][tt.y] != -1)
{
printf("%d\n",num1[t.x][t.y] + 1 + num2[tt.x][tt.y]);
return ;
}
if(inside(tt.x,tt.y) && num1[tt.x][tt.y] == -1)
{
num1[tt.x][tt.y] = num1[t.x][t.y] + 1;
p.push(tt);
}
}
}
size = q.size();
while(size --)
{
t = q.front();
q.pop();
if(inside(t.x,t.y) && num1[t.x][t.y] != -1)
{
printf("%d\n",num2[t.x][t.y] + num1[t.x][t.y] );
return ;
}
for(int i=0; i<8; i++)
{
tt.x = t.x + dirx[i];
tt.y = t.y + diry[i];
if(inside(tt.x,tt.y) && num1[tt.x][tt.y] != -1)
{
printf("%d\n",num2[t.x][t.y] + 1 + num1[tt.x][tt.y]);
return ;
}
if(inside(tt.x,tt.y) && num2[tt.x][tt.y] == -1)
{
num2[tt.x][tt.y] = num2[t.x][t.y] + 1;
q.push(tt);
}
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
init();
scanf("%d%d%d%d",&start.x,&start.y,&end.x,&end.y);
dbfs();
}
return 0;
}