P2060 [HNOI2006]马步距离

P2060 [HNOI2006]马步距离

数据到百万级别，明显爆搜不行，剪枝也没法剪。先打表。发现小数据内步数比较受位置关系影响，但数据一大就不影响了。大概搜了一个20*20的表把赋值语句打出来。判断时贪心，看两点间位置差，根据x差或者y差的大小比较来采取两种不同跳法，直到在小范围内再直接借助打的表加以输出。注意起点和目标的位置的及时调整（依据对称性，见line49），方便跳动。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #define dbg(x) cerr<<#x<<" = "<<x<<endl

 #define ddbg(x,y) cerr<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<endl

 using namespace std;

 typedef long long ll;

 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}

 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=;

 int step[N][N]={{,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,},

                 {,,,,,,,,,,,,,,,,,,,,}};

 inline void swap(int&x,int&y){x^=y^=x^=y;}

 int main(){//freopen("test.in","r",stdin);freopen("test.out","w",stdout);

     int sx,sy,tx,ty,ans=;

     read(sx),read(sy),read(tx),read(ty);

     if(sx>tx)swap(sx,tx);if(sy>ty)swap(sy,ty);

     while(tx-sx>=N||ty-sy>=N){//ddbg(sx,sy);

         if(ty-sy<tx-sx)sx+=,++sy;

         else ++sx,sy+=;++ans;

         if(sx>tx)swap(sx,tx);if(sy>ty)swap(sy,ty);

     }

     return printf("%d",ans+step[tx-sx][ty-sy]),;

 }