poj~1915(bfs)

Knight Moves
제목: 기점에서 종점까지 최소한 몇 걸음은 걸어야 한다.
위 양방향 검색 코드:

#include <stdio.h>
#include <string.h>
#include <queue>

using namespace std;

int n,sx,sy,ex,ey;
int dirx[]={-2,-2,-1,-1,1,1,2,2};   //   ，8   
int diry[]={1,-1,2,-2,2,-2,1,-1};

typedef struct point{   
    int x,y;
}point;

int step[305][305];     //   
int vis[305][305];      //                     


void bfs(){
    memset(step,0,sizeof(step));    
    memset(vis,0,sizeof(vis));
    point  start,end;   
    start.x=sx,start.y=sy;
    end.x=ex,end.y=ey;
    queue <point > q;
    q.push(start);  //    
    q.push(end);    //    
    vis[sx][sy]=1;  //        1
    vis[ex][ey]=2;  //       2

    while(!q.empty()){
        point temp=q.front();
        q.pop();
        for(int i=0;i<8;++i){
            point next=temp;
            next.x+=dirx[i];
            next.y+=diry[i];

            if(next.x<0 || next.y<0 || next.x>=n || next.y>=n) continue;    //  

            if(vis[next.x][next.y]==0){ //   
                q.push(next);
                vis[next.x][next.y]=vis[temp.x][temp.y];
                step[next.x][next.y]=step[temp.x][temp.y]+1;
            }
            else if(vis[next.x][next.y]!=vis[temp.x][temp.y]){  //     ，              
                printf("%d
",step[next.x][next.y]+step[temp.x][temp.y]+1);
                return ;
            }
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        scanf("%d %d",&sx,&sy);
        scanf("%d %d",&ex,&ey);
        if(sx==ex && sy==ey) printf("0
");
        else bfs();
    }
    return 0;
}