Description
求点(xs,ys)走马步到(xp,yp)的最小步数
Input
只包含4个整数，它们彼此用空格隔开，分别为xp,yp,xs,ys。并且它们的都小于10000000。
Output
含一个整数，表示从点p到点s至少需要经过的马步移动次数。
设起点与终点的坐标差为(x,y)
则问题转化为求向量方程a*(1,2)+b*(2,1)+c*(1,-2)+d*(2,-1)==(x,y)的解满足a,b,c,d为整数且绝对值之和最小。
由对称性可令0≤y≤x
使a*(1,2)+b*(2,1)接近(x,y)并求c,d
使b*(2,1)+d*(2,-1)接近(x,y)并求a,c
枚举即可
#include<cstdio> inline void mins(int&a,int b){if(a>b)a=b;} inline void abss(int&a){if(a<0)a=-a;} inline int abs(int a){return a>0?a:-a;} int main(){ int x,y,x2,y2,as,bs,cs,ds,ans=0x7fffffff; scanf("%d%d%d%d",&x,&y,&x2,&y2); x-=x2;y-=y2; abss(x);abss(y); if(x<y){int c=x;x=y;y=c;} int as0=(y*2-x)/3,bs0=(x*2-y)/3; for(as=as0-10;as<=as0+10;as++) for(bs=bs0-10;bs<=bs0+10;bs++){ int v1=x-as-bs*2,v2=2*as+bs-y; int v3=(v1+v2)/3; cs=v2-v3;ds=v1-v3; if(as+2*bs+cs+2*ds==x&&2*as+bs-2*cs-ds==y)mins(ans,abs(as)+abs(bs)+abs(cs)+abs(ds)); } bs0=(x+y*2)/4; int ds0=(x-y*2)/4; for(bs=bs0-10;bs<=bs0+10;bs++) for(ds=ds0-10;ds<=ds0+10;ds++){ int v1=x-bs*2-ds*2,v2=(y-bs+ds)/2; as=(v1+v2)/2;cs=(v1-v2)/2; if(as+2*bs+cs+2*ds==x&&2*as+bs-2*cs-ds==y)mins(ans,abs(as)+abs(bs)+abs(cs)+abs(ds)); } printf("%d",ans); return 0; }