题解 P1747 【好奇怪的游戏】

· · 题解

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

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

这个公式适用于所有除了(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));
}

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