记录编号	189844	评测结果	AAAAAAAAAA
题目名称	[HNOI 2006]马步距离	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2015-09-30 08:00:08	内存使用	3.49 MiB

#define ll long long
 
#define MAXN 210UL
 
#define BS(a) (a+6)
 
#include <cstdio>
#include <cstring>
#include <queue>
 
int a,b,xp,yp,xs,ys,Ans,f1,f2;
int dx[MAXN][MAXN];
bool ex[MAXN][MAXN];
int op1[9]={0,1,-1,-2,-2,-1, 1, 2,2};
int op2[9]={0,2, 2, 1,-1,-2,-2,-1,1};
 
std::queue<int> quex,quey;
 
inline ll ABS(ll r){return r>0?r:-r;}
inline bool Check(ll x,ll y){return x>=0&&y>=0&&a-x-(y<<1)>=0&&b-(x<<1)-y>=0;}
inline void Update(ll x,ll y){for(ll i=x-5;i<=x+5;i++) for(ll j=y-5;j<=y+5;j++) if(i+j>f1+f2&&Check(i,j)) f1=i,f2=j;return;}
inline void Push(int x,int y){quex.push(x),quey.push(y);return;}
inline bool Pos(int x,int y){return x>=-5&&y>=-5&&x<=a+10&&y<=b+10;}
 
//x=op1 (1,2)  y=op2 (2,1)
//e1:a-x-2y>=0 e2:b-2x-y>=0  ==> e3: z=x+y  f1,f2;
//P1 (0,a/2) .. P2(a,0)   .. 
//P3 (0,b)   .. P4(b/2,0) ..
//P5 ((2b-a)/3,(2a-b)/3)
 
bool flag;
 
void spfa(){
    memset(dx,50,sizeof(dx));dx[BS(0)][BS(0)]=0;
    Push(0,0);
    while(!quex.empty()){
        int tx=quex.front(),ty=quey.front();quex.pop(),quey.pop();ex[tx][ty]=0;
        for(int i=1,nx,ny;i<=8;i++){
            nx=tx+op1[i],ny=ty+op2[i];
            if(!Pos(nx,ny)) continue;
            if(dx[BS(nx)][BS(ny)]>dx[BS(tx)][BS(ty)]+1){
                dx[BS(nx)][BS(ny)]=dx[BS(tx)][BS(ty)]+1;
                if(!ex[BS(nx)][BS(ny)]){
                    ex[BS(nx)][BS(ny)]=1;
                    Push(nx,ny);
                }
            }
        }
    }
    Ans+=dx[BS(a)][BS(b)];
    return;
}
 
int main(){
	freopen("horsed.in","r",stdin);
	freopen("horsed.out","w",stdout);
    scanf("%d%d%d%d",&xp,&yp,&xs,&ys);
    a=ABS(xp-xs),b=ABS(yp-ys);
    if(a>50&&b>50) flag=true,a-=20,b-=20;
    if(flag){
        Update(0,a>>1);Update(a,0);Update(0,b);Update(b>>1,0);Update(((b<<1)-a)/3,((a<<1)-b)/3);
        a-=f1+(f2<<1),b-=(f1<<1)+f2;Ans=f1+f2;
    }
    if(a>b&&a>20) Ans+=(((a-20)>>2)-1)<<1,a-=(((a-20)>>2)-1)<<2;
    else if(b>20) Ans+=(((b-20)>>2)-1)<<1,b-=(((b-20)>>2)-1)<<2;
    if(flag) a+=20,b+=20;
    spfa();
    printf("%d",Ans);
    return 0;
}