1285: [Hnoi2006]马步距离

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 36  Solved: 16

[][][]

Description

在国际象棋和中国象棋中，马的移动规则相同，都是走“日”字，我们将这种移动方式称为马步移动。如右图所示，从标号为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 至少需要经过多少次马步移动？

Input

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

Output

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

Sample Input

1 2 7 9

Sample Output

5

HINT

 

Source

1 #include 
      
        2 using namespace std;  3 int dx[8]={
    1,1,-1,-1,2,2,-2,-2}; 4 int dy[8]={
    2,-2,2,-2,1,-1,1,-1}; 5 int a,b,c,d,x,y,ans; 6 int px[100000]; 7 int py[100000]; 8 int h[30][30]; 9 bool v[30][30];10 11 void bfs()12 {13     int head,tail,xx,yy,x,y,i;14     head=0;15     tail=1;16     px[1]=0;17     py[1]=0;18     memset(h,127,sizeof(h));19     h[0][0]=0;20     while (head!=tail)21     {22         head++;23         x=px[head];24         y=py[head];25         v[x][y]=false;26         for (i=0;i<8;i++)27         {28             xx=x+dx[i];29             yy=y+dy[i];30             if (xx>-10 && xx<20 && yy>-10 && yy<20)31             if (h[xx][yy]>h[x][y]+1)32             {33                 h[xx][yy]=h[x][y]+1;34                 if (!v[xx][yy])35                 {36                     tail++;37                     px[tail]=xx;38                     py[tail]=yy; 39                     v[x][y]=true; 40                 }41             }42         }43     }44 }45 46 int main()47 {48     cin>>a>>b>>c>>d;49     x=abs(a-c);50     y=abs(b-d);51     bfs();52     while (x>=10 || y>=10)53     {54         if (x>y)55         {56             x=x-2;57             y=y-1;58         }59         else60         {61             x=x-1;62             y=y-2;63         }64         ans++;65         x=abs(x);66         y=abs(y);67     }68     ans=ans+h[x][y];69     cout<
       
        <