HDU 2243 Knight Moves

1433 ワード

これは簡単なBFSの広い検索のテーマです.絵が読めないなら、助けになるはずです.
#include 
#include 
int x1,x2,y1,y2,count;
int z[9][9];
int h[8][2]={{-1,-2},{-2,-1},{-2,1,},{-1,2},{1,2},{2,1},{1,-2},{2,-1}};
char t1,t2;
struct sa
{
    int x,y,step;
}data[100];
int bfs(int x,int y)
{
    int r=0,l=0;
    data[r].x=x;
    data[r].y=y;
    data[r++].step=0;
    z[x][y]=1;
    if (x==x2&&y==y2) return 0;
    while (l=1&&next.x<=8&&next.y>=1&&next.y<=8&&z[next.x][next.y]==0)
            {
                if (next.x==x2&&next.y==y2) return next.step;
                z[next.x][next.y]=1;
                data[r].x=next.x;
                data[r].y=next.y;
                data[r++].step=next.step;
            }
        }
    }
    return -1;
}
int main()
{
    while (scanf("%c%d %c%d",&t1,&y1,&t2,&y2)!=EOF)
    {
        x1=t1-'a'+1;
        x2=t2-'a'+1;
        //printf("%d %d %d %d",x1,x2,y2,y1);
        memset(z,0,sizeof(z));
        count=bfs(x1,y1);
        printf("To get from %c%d to %c%d takes %d knight moves.
",t1,y1,t2,y2,count); count=0; getchar(); } return 0; }