随笔-20  评论-16  文章-36  trackbacks-0
      以前没过的一道题,今天又看到,感觉很轻易就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<&& 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 古月残辉 阅读(408) 评论(0)  编辑 收藏 引用 所属分类: POJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理