本来不想写的,但是这个题目可以用双向广搜来做,所以也就写写吧。地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1915
#include < stdio.h >
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include < stdlib.h >
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int hash[301][301][2];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int l;
int c;
int count;
}type;
type q1[50000];
int h1, t1;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
type q2[50000];
int h2, t2;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int move[8][2] = { -2, 1, -1, 2, 1, 2, 2, 1, 2, -1, 1, -2, -1, -2, -2, -1 };
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void inith( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( int j=0; j<n; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( int z=0; z<2; z++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
hash[i][j][z] = 0;
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void initq()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
h1 = h2 = 0;
t1 = t2 = -1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void in1( type *a )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
t1 ++;
q1[t1].l = a->l;
q1[t1].c = a->c;
q1[t1].count = a->count;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void out1( type *a )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
a->l = q1[h1].l;
a->c = q1[h1].c;
a->count = q1[h1].count;
h1 ++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int testempty1()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( h1 > t1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void in2( type *a )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
t2 ++;
q2[t2].l = a->l;
q2[t2].c = a->c;
q2[t2].count = a->count;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void out2( type *a )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
a->l = q2[h2].l;
a->c = q2[h2].c;
a->count = q2[h2].count;
h2 ++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int testempty2()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( h2 > t2 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cmp( const void *a, const void *b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return *( ( int * )a + 2 ) - *( ( int * )b + 2 );
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int dbfs( type *s, type *t, int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i, j;
type a, b;
int tl, tc;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int temp[9][3];
int len;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int ans = 100000;
inith( n );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
initq();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
in1( s );
hash[s->l][s->c][0] = s->count;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
in2(t);
hash[t->l][t->c][1] = t->count;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( !testempty1() || !testempty2() )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( !testempty1() )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
out1( &a );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( hash[a.l][a.c][1] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return hash[a.l][a.c][0] + hash[a.l][a.c][1] - 2;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
len = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=0; i<8; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
tl = a.l + move[i][0];
tc = a.c + move[i][1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( tl>=0 && tl<n && tc>=0 && tc<n && !hash[tl][tc][0] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
temp[len][0] = tl;
temp[len][1] = tc;
temp[len][2] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( j=0; j<8; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
tl = temp[len][0] + move[j][0];
tc = temp[len][1] + move[j][1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( tl>=0 && tl<n && tc>=0 && tc<n && !hash[tl][tc][0] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
temp[len][2] ++;
}
}
len ++;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
qsort( temp, len, sizeof( temp[0] ), cmp );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=0; i<len; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
b.l = temp[i][0];
b.c = temp[i][1];
b.count = a.count + 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
in1( &b );
hash[b.l][b.c][0] = b.count;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( !testempty2() )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
out2( &a );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( hash[a.l][a.c][0] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return hash[a.l][a.c][0] + hash[a.l][a.c][1] - 2;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
len = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=0; i<8; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
tl = a.l + move[i][0];
tc = a.c + move[i][1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( tl>=0 && tl<n && tc>=0 && tc<n && !hash[tl][tc][1] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
temp[len][0] = tl;
temp[len][1] = tc;
temp[len][2] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( j=0; j<8; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
tl = temp[len][0] + move[j][0];
tc = temp[len][1] + move[j][1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( tl>=0 && tl<n && tc>=0 && tc<n && !hash[tl][tc][1] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
temp[len][2] ++;
}
}
len ++;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
qsort( temp, len, sizeof( temp[0] ), cmp );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=0; i<len; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
b.l = temp[i][0];
b.c = temp[i][1];
b.count = a.count + 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
in2( &b );
hash[b.l][b.c][1] = b.count;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int T, n;
type s, t;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
scanf( "%d", &T );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( T-- )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf( "%d", &n );
scanf( "%d%d", &s.l, &s.c );
s.count = 1;
scanf( "%d%d", &t.l, &t.c );
t.count = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf( "%d\n", dbfs( &s, &t, n ) );
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
29 | 30 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|