Summary

洛谷 P2060 [HNOI2006]马步距离 的题解,
算法为 打表 贪心 .

Link

题目链接

Text

满篇的 Judging/Waiting 我也是醉了

这道题先看 30% 的数据 (我们老师给的题), 范围是

30%:|xp-xs|<=10,|yp-ys|<=5

100%:xp,yp,xs,ys<=10000000

所以可以打表.

接着想优化：将整个坐标系对称之后, 两个点的相对位置不变, 所以可以让马在左下角, 往右上角走. 这样打表只打11*6的范围就可以了.

接着想剩下的 70%, 在距离目标较远的时候可以贪心, 接近了就不容易贪心了, 于是可以接着打表.

inline double len(int x,int y) {return sqrt((x-xs)*(x-xs)+(y-ys)*(y-ys));}

if (len(xp+1,yp+2)<len(xp+2,yp+1)) {xp+=1; yp+=2;}

我第一次就是贪心时用了上面那段代码, 于是 WA 了两个点.

Code

#include <cmath>
#include <cstdio>
using namespace std;

int xp,yp,xs,ys,ans,m[100]={0,3,2,3,2,3,4,5,4,5,6,3,2,1,2,3,4,3,4,5,6,5,2,1,4,3,2,3,4,5,4,5,6,3,2,3,2,3,4,3,4,5,6,5,2,3,2,3,4,3,4,5,4,5,6,3,4,3,4,3,4,5,4,5,6,5};

inline void swap(int &a,int &b) {int c=a; a=b; b=c;}

int main()
{
    scanf ("%d%d%d%d",&xp,&yp,&xs,&ys);
    if (xp>xs) swap(xp,xs);
    if (yp>ys) swap(yp,ys);//确保马在左下角
    if (xs-xp<6&&ys-yp<11) printf ("%d",m[(xs-xp)*11+ys-yp]);//如果可以直接贪心
    else while (1)
    {
        if (xp>xs) swap(xp,xs);
        if (yp>ys) swap(yp,ys);//确保马在左下角
        if (xs-xp<6&&ys-yp<11)//如果接近了
        {
            printf ("%d",ans+m[(xs-xp)*11+ys-yp]);
            return 0;
        }
        if (xp-xs>yp-ys) {xp+=1; yp+=2;}
        else {xp+=2; yp+=1;}//贪心
        ++ans;
    }
    return 0;
}