学步园

POJ_2243

    在读入并转化起点与终点之后，只需要从起点开始，对周围8个可达的位置进行广搜并依次记录到达该位置时的步数，当搜到终点的时候退出循环即可。

#include<stdio.h>
#include<string.h>
char s[5],t[5],sx,sy,tx,ty;
int a[10][10],dis[10][10],qx[100],qy[100];
int dx[]={-1,-2,-2,-1,1,2,2,1},dy[]={-2,-1,1,2,2,1,-1,-2};
int main()
{
int i,x,y,newx,newy,front,rear,min;
while(scanf("%s%s",s,t)==2)
    {
        memset(a,-1,sizeof(a));
        sx=s[0]-'a';
        sy=s[1]-'1';
        tx=t[0]-'a';
        ty=t[1]-'1';
        memset(dis,-1,sizeof(dis));
        dis[sx][sy]=0;
        front=rear=0;
        qx[rear]=sx;
        qy[rear]=sy;
        rear++;
while(front<rear)
        {
            x=qx[front];
            y=qy[front];
if(x==tx&&y==ty)
break;
            front++;
for(i=0;i<8;i++)
            {
                newx=x+dx[i];
                newy=y+dy[i];
if(dis[newx][newy]<0&&newx>=0&&newx<8&&newy>=0&&newy<8)
                {
                    dis[newx][newy]=dis[x][y]+1;
                    qx[rear]=newx;
                    qy[rear]=newy;
                    rear++;
                }
            }
        }
        min=dis[tx][ty];
        printf("To get from %s to %s takes %d knight moves.\n",s,t,min);
    }
return 0;    
}