记录编号	190617	评测结果	AAAAAAAAAA
题目名称	[HNOI 2006]马步距离	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2015-10-03 21:15:05	内存使用	0.31 MiB

#include<cstdio>
#include<queue>

using namespace std;

struct Ver{
	int x,y,bs;
}c,p;

int ABS(int k)
{
	return k>(-k)?k:(-k);
}

int xc,yc;
int x1,y1,x2,y2,bs;

queue<Ver>q;

int main()
{
	freopen("horsed.in","r",stdin);
	freopen("horsed.out","w",stdout);
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	while(true){
		xc=ABS(x1-x2);yc=ABS(y1-y2);
		if(xc<=5&&yc<=5)break;
		if(yc>=xc){
			if(x2>x1){
				x1+=1;
				if(y2>y1)y1+=2;
				else y1-=2;
			}else{
				x1-=1;
				if(y2>y1)y1+=2;
				else y1-=2;
			}
		}else{
            if(x2>x1){
				x1+=2;
				if(y2>y1)y1+=1;
				else y1-=1;
			}else{
				x1-=2;
				if(y2>y1)y1+=1;
				else y1-=1;
			}
		}bs++;
	}c.x=x1;c.y=y1;c.bs=bs;q.push(c);
	while(true){
		p=q.front();q.pop();c.bs=p.bs+1;
		if(p.x==x2&&p.y==y2){
			printf("%d",p.bs);
			return 0;
		}
		c.x=p.x+2;c.y=p.y+1;q.push(c);
		c.x=p.x+2;c.y=p.y-1;q.push(c);
		c.x=p.x-2;c.y=p.y+1;q.push(c);
		c.x=p.x-2;c.y=p.y-1;q.push(c);
		c.x=p.x+1;c.y=p.y+2;q.push(c);
		c.x=p.x+1;c.y=p.y-2;q.push(c);
		c.x=p.x-1;c.y=p.y+2;q.push(c);
		c.x=p.x-1;c.y=p.y-2;q.push(c);
	}
}