本来不想写的,但是这个题目可以用双向广搜来做,所以也就写写吧。地址: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= -21-1212212-11-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
->= q1[h1].l;
    a
->= 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
->= q2[h2].l;
    a
->= 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<&& 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<&& tc>=0 && tc<&& !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<&& tc>=0 && tc<&& !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<&& tc>=0 && tc<&& !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;
}