BZOJ 1193--马步距离

Enterprise_

发布于 2019-02-20 10:41:52

3770

发布于 2019-02-20 10:41:52

文章被收录于专栏：小L的魔法馆小L的魔法馆

1193: [HNOI2006]马步距离

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 2267 Solved: 1026

Description

在国际象棋和中国象棋中，马的移动规则相同，都是走“日”字，我们将这种移动方式称为马步移动。如图所示，

从标号为 0 的点出发，可以经过一步马步移动达到标号为 1 的点，经过两步马步移动达到标号为 2 的点。任给

平面上的两点 p 和 s ,它们的坐标分别为 (xp,yp) 和 (xs,ys) ,其中，xp，yp，xs，ys 均为整数。从 (xp,yp)

出发经过一步马步移动可以达到 (xp+1,yp+2)、(xp+2,yp+1)、(xp+1,yp-2)、(xp+2,yp-1)、(xp-1,yp+2)、(xp-2,

yp+1)、(xp-1,yp-2)、(xp-2,yp-1)。假设棋盘充分大，并且坐标可以为负数。现在请你求出从点 p 到点 s 至少

需要经过多少次马步移动？

Input

只包含4个整数，它们彼此用空格隔开，分别为xp,yp,xs,ys。并且它们的都小于10000000。

Output

含一个整数，表示从点p到点s至少需要经过的马步移动次数。

Sample Input

1 2 7 9

Sample Output

HINT

Source

这道题和camp上的knight何其相似啊，唯一的区别在与这里是从一个点到另一个点，所以两个点相减就可以变成从(0,0)到任意点了

#include <cstdio>
#include <cstring>
#include <cmath>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;

ll fun(ll x, ll y) {

    if (x == 1 && y == 0) {
        return 3;
    }
    if (x == 2 && y == 2) {
        return 4;
    }
    ll delta = x - y;
    if (y>delta) {
        return delta - 2 * floor(((double)(delta - y)) / 3.0);
    }
    else {
        return delta - 2 * floor(((double)(delta - y)) / 4.0);
    }
}

int main()
{
        ll x1, y1, a, b;
        cin >> x1 >> y1 >> a >> b;
        ll c = abs(x1 - a), d =abs( y1 - b);
        if (c < d)
            swap(c, d);
        cout << abs(fun(c, d)) << endl;
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018年08月11日，如有侵权请联系 cloudcommunity@tencent.com 删除

input