本来不想写的，但是这个题目可以用双向广搜来做，所以也就写写吧。地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1915

#include < stdio.h >

#include < stdlib.h >

int hash[301][301][2];

typedef struct
{
    int l;
    int c;
    int count;
}type;
type q1[50000];
int h1, t1;

type q2[50000];
int h2, t2;

int move[8][2] = { -2, 1, -1, 2, 1, 2, 2, 1, 2, -1, 1, -2, -1, -2, -2, -1 };

void inith( int n )
{

    for ( int i=0; i<n; i++ )
    {
        for ( int j=0; j<n; j++ )
        {
            for ( int z=0; z<2; z++ )
            {
                hash[i][j][z] = 0;
            }
        }
    }
}

void initq()
{

    h1 = h2 = 0;
    t1 = t2 = -1;
}

void in1( type *a )
{

    t1 ++;
    q1[t1].l = a->l;
    q1[t1].c = a->c;
    q1[t1].count = a->count;
}

void out1( type *a )
{

    a->l = q1[h1].l;
    a->c = q1[h1].c;
    a->count = q1[h1].count;
    h1 ++;
}

int testempty1()
{

    if ( h1 > t1 )
    {
        return 1;
    }

    return 0;
}

void in2( type *a )
{

    t2 ++;
    q2[t2].l = a->l;
    q2[t2].c = a->c;
    q2[t2].count = a->count;
}

void out2( type *a )
{

    a->l = q2[h2].l;
    a->c = q2[h2].c;
    a->count = q2[h2].count;
    h2 ++;
}

int testempty2()
{

    if ( h2 > t2 )
    {
        return 1;
    }

    return 0;
}

int cmp( const void *a, const void *b )
{

    return *( ( int * )a + 2 )  - *( ( int * )b + 2 );
}

int dbfs( type *s, type *t, int n )
{

    int i, j;
    type a, b;
    int tl, tc;

    int temp[9][3];
    int len;

    int ans = 100000;
    
    inith( n );

    initq();

    in1( s );
    hash[s->l][s->c][0] = s->count;

    in2(t);
    hash[t->l][t->c][1] = t->count;

    while (  !testempty1() || !testempty2() )
    {
        if ( !testempty1() )
        {
            out1( &a );

            if ( hash[a.l][a.c][1] )
            {
                return hash[a.l][a.c][0] + hash[a.l][a.c][1] - 2;
            }

            len = 0;

            for ( i=0; i<8; i++ )
            {
                tl = a.l + move[i][0];
                tc = a.c + move[i][1];

                if ( tl>=0 && tl<n && tc>=0 && tc<n  && !hash[tl][tc][0] )
                {
                    temp[len][0] = tl;
                    temp[len][1] = tc;
                    temp[len][2] = 0;

                    for ( j=0; j<8; j++ )
                    {
                        tl = temp[len][0] + move[j][0];
                        tc = temp[len][1] + move[j][1];

                        if ( tl>=0 && tl<n && tc>=0 && tc<n && !hash[tl][tc][0] )
                        {
                            temp[len][2] ++;
                        }
                    }
                    len ++;
                }
            }

            qsort( temp, len, sizeof( temp[0] ), cmp );

            for ( i=0; i<len; i++ )
            {
                b.l = temp[i][0];
                b.c = temp[i][1];
                b.count = a.count + 1;

                in1( &b );
                hash[b.l][b.c][0] = b.count;
            }
        }

        if ( !testempty2() )
        {
            out2( &a );

            if ( hash[a.l][a.c][0] )
            {
                return hash[a.l][a.c][0] + hash[a.l][a.c][1] - 2;
            }

            len = 0;

            for ( i=0; i<8; i++ )
            {
                tl = a.l + move[i][0];
                tc = a.c + move[i][1];

                if ( tl>=0 && tl<n && tc>=0 && tc<n && !hash[tl][tc][1] )
                {
                    temp[len][0] = tl;
                    temp[len][1] = tc;
                    temp[len][2] = 0;

                    for ( j=0; j<8; j++ )
                    {
                        tl = temp[len][0] + move[j][0];
                        tc = temp[len][1] + move[j][1];

                        if ( tl>=0 && tl<n && tc>=0 && tc<n && !hash[tl][tc][1] )
                        {
                            temp[len][2] ++;
                        }
                    }
                    len ++;
                }
            }        

            qsort( temp, len, sizeof( temp[0] ), cmp );

            for ( i=0; i<len; i++ )
            {
                b.l = temp[i][0];
                b.c = temp[i][1];
                b.count  = a.count + 1;

                in2( &b );
                hash[b.l][b.c][1] = b.count;
            }
        }
    }

    return 0;
}

int main()
{

    int T, n;
    type s, t;

    scanf( "%d", &T );

    while ( T-- )
    {
        scanf( "%d", &n );
        scanf( "%d%d", &s.l, &s.c );
        s.count = 1;
        scanf( "%d%d", &t.l, &t.c );
        t.count = 1;

        printf( "%d\n", dbfs( &s, &t, n ) );
    }
    return 0;
}