BZOJ 1193 搜索+贪心

预处理出100*100以内的最优解

贪心走日

判断是0*4还是2*4

搞定

//By SiriusRen
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
int sx,sy,ex,ey,vis[105][105],ans;
char xx[]={2,2,1,1,-1,-1,-2,-2},yy[]={1,-1,2,-2,2,-2,1,-1};
bool check(int x,int y){
    return x>=1&&x<=100&&y>=1&&y<=100;
}
void BFS(){
    queue<pair<int,int> >q;
    q.push(make_pair(50,50));
    vis[50][50]=1;
    while(!q.empty()){
        int dx=q.front().first,dy=q.front().second;q.pop();
        for(int i=0;i<8;i++){
            int tx=dx+xx[i],ty=dy+yy[i];
            if(check(tx,ty)&&!vis[tx][ty]){
                vis[tx][ty]=vis[dx][dy]+1;
                q.push(make_pair(tx,ty));
            }
        }
    }
}
int main(){
    scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
    BFS();
    int rx=abs(sx-ex),ry=abs(sy-ey);
    while(rx+ry>50){
        if(rx<ry)swap(rx,ry);
        if(ry>2)rx-=4,ry-=2;
        else rx-=4;
        ans+=2;
    }
    ans+=vis[rx+50][ry+50];
    printf("%d
",ans-1);
}