POJ 1915 经典马步 双向bfs

拿这个经典题目开刀...........可是双向时间优势在这题上的效果不太明显

#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
",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
",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
",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
",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;
}