BZOJ1193: [HNOI2006]馬步距離

易水人去，明月如霜。

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

5 思路：大範圍貪心，靠近目标點，小範圍直接BFS

代碼：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int read()
{
    char ch;int s=0,f=1;ch=getchar();
    while(ch>'9'||ch<'0') { if(ch=='-') f*=-1; ch=getchar(); }
    while(ch<='9'&&ch>='0') s=s*10+ch-48,ch=getchar();
    return s*f;
}
struct node {
 int x,y;
};
int x,y;
int xp,yp,xs,ys;
int ans=0;
int dis[105][105];
int xx[8]={1,1,-1,-1,2,2,-2,-2},yy[8]={2,-2,2,-2,1,-1,1,-1};
int qx[10005],qy[10005];

void bfs()
{
    memset(dis,-1,sizeof(dis));
    dis[x][y]=0;
    queue<node> q;
    node s; s.x=x,s.y=y;
    q.push(s);
    while(!q.empty())
    {
        node now=q.front();q.pop();
        for(int i=0;i<8;i++)
        {
            int dx,dy; dx=now.x+xx[i],dy=now.y+yy[i];
            if(dx<0||dy<0||dx>100||dy>100) continue;
            if(dis[dx][dy]!=-1) continue ;
            dis[dx][dy]=dis[now.x][now.y]+1;
            node dd; dd.x=dx,dd.y=dy;
            q.push(dd); if(dx==50&&dy==50) return ;
        }
    }
}

int main()
{
    xp=read(),yp=read(),xs=read(),ys=read();
    x=abs(xp-xs),y=abs(yp-ys);
    while(x+y>=50)
    {
        if(x<y) swap(x,y);
        if(x-4>=2*y) x-=4;
        else x-=4,y-=2;
        ans+=2;
    }
    x+=50,y+=50;

    bfs();
    printf("%d\n",ans+dis[50][50]);
 return 0;
}