自动搬运

查看原文

来自洛谷，原作者为

	snaptrap **

搬运于2025-08-24 21:28:37，当前版本为作者最后更新于2019-02-10 22:30:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

书上说这道题无法使用数学方法，因为有两种走法。我偏不信，只用了一个小时就推算出了一个公式：

s4=s3+s2+(x+y-s2*3)/4;

• 解释一下，x代表行坐标，y代表列坐标
• s1是x与y的差
• s2是s1除以4的余数
• s3是s1除以4的商
• s4是最终得数

这个公式适用于所有除了(1,2)和(2,1)的情况，就是(10^8,10^9)也能求出正确答案。首先我们画一条对角线，沿着对角线让马走象步，所用步数最少。所以我们要想办法让处在对角线以外的马飞入对角线。因为象步相对比“飞日”快（不绝对，“飞日”在某些情况下比较精确），所以用象步慢慢逼近对角线，再用“飞日”准确插入到对角线中，步数一定最少。

如果本来就在对角线上，即x==y，那么飞到(1,1)的步数为x/2（x>=3，其余加特判）。飞入对角线只需看行列的差是否是4的倍数（拿(16,12)举例，象步即(x-2,y+2)，移项得(x+4,y)，x-y=4,4是4的倍数，所以可以直接飞入对角线），若有余数，则飞到象步所能飞到的最大位置，用“飞日”飞。 飞入对角线的步数为**(x-y)/4+余数**，两者相加就可求出最短路径。

#include <cstdio>
int i,j,k,m,n,l,o,p,x,y;
int sum(int x,int y)
{
	int t,i,j,s1,s2,s3,s4;
	if(x<y)//有可能x<y,所以交换一下以便求差
	{
		t=x; 
		x=y;
		y=t;
	}
	if(x==2&&y==1) return 2;
	else if(x==2&&y==2) return 3;
    //这两个点过不去，特殊判定
	s1=x-y;//求差
	s2=s1%4;//余数
	s3=s1/4;//商
	s4=s3+s2+(x+y-s2*3)/4;
	return s4;
    /*细节：发现这个return s4不写，函数仍然返回s4的
    值因为定义在函数内部（包括main()）的变量用栈来分
    配空间，所以有时是随机数。
    在函数外部的变量用static
    分配，值总是0。函数的返回值在栈底（返回给
    main()，c++用ESP做栈寄存器），这个s4恰好就是栈
    底，如果没有定义变量的话栈底就是随机数了
    所以不写return也可以，大家可以试一试*/
 } 
int main()
{
	int a,b,c,d;
	scanf("%d%d",&a,&b);
	printf("%d\n",sum(a,b));
	scanf("%d%d",&c,&d);
	printf("%d",sum(c,d));
} 

我熬夜写的，可能有些啰嗦，恳求管理员帮忙挂在首页！