[bzoj 1193--HNOI2006]馬步距離

在國際象棋和中國象棋中，馬的移動規則相同，都是走“日”字，我們将這種移動方式稱為馬步移動。如圖所示， 從标号為 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 至少需要經過多少次馬步移動？

好吧，這道題看到這麼大的範圍，就肯定單純的bfs是不能解決的。但我們發現其實可以貪心，如果距離過大，走法就很單一，就會一直往終點靠，那麼我們就可以把大範圍馬上轉化為小範圍的bfs。那這道題就解決了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
struct node
{
    int x,y;
}list[];
int ss=;
int f[][];
bool v[][];
int dx[]={,,,,-,-,-,-};
int dy[]={,,-,-,,,-,-};
int bfs(int xx,int yy)
{
    memset(f,,sizeof(f));
    int head=,tail=;
    list[].x=,list[].y=;f[][]=;v[][]=true;
    while(head<=tail)
    {
        node tno=list[head];
        for(int i=;i<;i++)
        {
            tno.x=list[head].x+dx[i];
            tno.y=list[head].y+dy[i];
            if(f[tno.x][tno.y]>f[list[head].x][list[head].y]+)
            {
                f[tno.x][tno.y]=f[list[head].x][list[head].y]+;
                if(v[tno.x][tno.y]==false)
                {
                    v[tno.x][tno.y]=true;
                    list[++tail]=tno;
                    if(tno.x==xx && tno.y==yy)return f[xx][yy];
                }
            }
        }
        head++;
        v[list[head].x][list[head].y]=false;
    }
}
int main()
{
    int sx,sy,ex,ey,x,y,ans=;
    scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
    x=abs(sx-ex);y=abs(sy-ey);
    while(x>= || y>=)
    {
        if(x>y)x-=,y-=;
        else x-=,y-=;
        ans++;
        x=abs(x);y=abs(y);
    }
    printf("%d\n",ans+bfs(x,y));
    return ;
}