题目描述

 

在国际象棋和中国象棋中，马的移动规则相同，都是走“日”字，我们将这种移动方式称为马步移动。如图所示，

从标号为 0 的点出发，可以经过一步马步移动达到标号为 1 的点，经过两步马步移动达到标号为 2 的点。任给

平面上的两点 p 和 s ,它们的坐标分别为 (xp,yp) 和 (xs,ys) ,其中，xp，yp，xs，ys 均为整数。从 (xp,yp) 

出发经过一步马步移动可以达到 (xp+1,yp+2)、(xp+2,yp+1)、(xp+1,yp-2)、(xp+2,yp-1)、(xp-1,yp+2)、(xp-2,

yp+1)、(xp-1,yp-2)、(xp-2,yp-1)。假设棋盘充分大，并且坐标可以为负数。现在请你求出从点 p 到点 s 至少

需要经过多少次马步移动？

输入

只包含4个整数，它们彼此用空格隔开，分别为xp,yp,xs,ys。并且它们的都小于10000000。

输出

含一个整数，表示从点p到点s至少需要经过的马步移动次数。

样例输入

1 2 7 9

样例输出

5

题解

 

 

 

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 int u[10]={
    1,1,2,2,-1,-1,-2,-2},p[10]={
    2,-2,1,-1,2,-2,1,-1}; 6 int sx,sy,ex,ey; 7 int q[10005][3]; 8 int ans,dis[105][105]; 9 bool ok(int x,int y)10 {11     if(x<0||y<0||x>100||y>100)return false;12     return true;13 }14 void bfs(int x,int y)15 {16     memset(dis,-1,sizeof(dis));17     int head=0,tail=1;18     q[0][0]=x;q[0][1]=y;dis[x][y]=0;19     while(head!=tail)20     {21         int xx=q[head][0],yy=q[head++][1];22         for(int i=0 ; i<8 ; ++i)23         {24             int dx=u[i]+xx;25             int dy=p[i]+yy;26             if(!ok(dx,dy)||dis[dx][dy]!=-1)continue;27             dis[dx][dy]=dis[xx][yy]+1;28             if(dx==50&&dy==50)return ;29             q[tail][0]=dx;q[tail++][1]=dy;30         }31     }32 }33 int main()34 {35     scanf("%d%d%d%d",&sx,&sy,&ex,&ey);36     int x=abs(sx-ex),y=abs(sy-ey);37     while(x+y>=50)38     {39         if(x