以前没过的一道题，今天又看到，感觉很轻易就A了。
这是一道很简单的搜索题，可以用双向广搜，我用一个数组chbd[][]记录搜索状态，初始全为-1，向前搜索过记为0，向后搜索过记为1，再用一个step[i][j]记录搜索到i行j列时用的步数，最后只要判断相遇即可。相遇的条件是向前搜索到chbd[][]=1或者向后搜索到chbd[][]=0的点。
下面是我的实现代码：
#include <iostream>
using namespace std;
int step[301][301], chbd[301][301], ox, oy, dx, dy, n;
struct Node{
int x, y;
}node[90001];
Node *h1, *t1, *h2, *t2;
int dir[8][2]= {1,2,2,1,1,-2,2,-1,-1,2,-1,-2,-2,-1,-2,1};
bool isValid( int tx, int ty ){
return ( tx>=0 && tx<n && ty>=0 && ty<n );
}
int biBFS(){
int tx, ty, i;
while( h1!=t1 && h2!=t2 ){
if( h1!=t1 ){
for( i= 0; i< 8; i++ ){
tx= h1->x+ dir[i][0];
ty= h1->y+ dir[i][1];
if( isValid( tx, ty ) && chbd[tx][ty]!=0 ){
if( chbd[tx][ty]==1 )
return step[h1->x][h1->y]+step[tx][ty]+1;
t1->x= tx;
t1->y= ty;
t1++;
chbd[tx][ty]= 0;
step[tx][ty]= step[h1->x][h1->y]+1;
}
}
h1++;
}
if( h2!=t2 ){
for( i= 0; i< 8; i++ ){
tx= h2->x+ dir[i][0];
ty= h2->y+ dir[i][1];
if( isValid( tx, ty ) && chbd[tx][ty]!=1 ){
if( chbd[tx][ty]==0 )
return step[h2->x][h2->y]+step[tx][ty]+1;
t2->x= tx;
t2->y= ty;
t2--;
chbd[tx][ty]= 1;
step[tx][ty]= step[h2->x][h2->y]+1;
}
}
h2--;
}
}
return -1;
}
int main(){
int m;
scanf("%d",&m);
while( m-- ){
scanf("%d%d%d%d%d",&n,&ox,&oy,&dx,&dy);
if( ox==dx && oy==dy ){
puts("0");
continue;
}
memset(chbd,-1,sizeof(chbd));
h1= node;
h1->x= ox;
h1->y= oy;
chbd[ox][oy]= 0;
step[ox][oy]= 0;
t1= node+1;
h2= node+90000;
h2->x= dx;
h2->y= dy;
chbd[dx][dy]= 1;
step[dx][dy]= 0;
t2= h2-1;
printf("%d\n",biBFS());
}
return 0;
}
posted on 2009-06-22 13:52
古月残辉 阅读(395)
评论(0) 编辑 收藏 引用 所属分类:
POJ