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。

代码:

#include <bits/stdc++.h>
#define G 20
using namespace std;
struct Point{
    int x,y,n;
};
const int fx[]={1,2,-1,-2,1,2,-1,-2},
          fy[]={2,1,2,1,-2,-1,-2,-1};
bool vis[55][55];
int bfs(int x,int y){
    queue<Point> q;
    q.push((Point){0,0,0});
    vis[G][G]=0;
    while(!q.empty()){
        Point p=q.front();
        q.pop();
        if(p.x==x&&p.y==y)
            return p.n;
        for(int i=0;i<8;i++){
            int nx=p.x+fx[i],ny=p.y+fy[i];
            if(nx>-10&&nx<20&&ny>-10&&ny<20)
                if(!vis[nx+G][ny+G]){
                    vis[nx+G][ny+G]=true;
                    q.push((Point){nx,ny,p.n+1});
                }
        }
    }
    return -1;
}
int main(){
    long long x,y,tx,ty,ans=0;
    ios::sync_with_stdio(false);
    cin>>x>>y>>tx>>ty;
    x=abs(x-tx);
    y=abs(y-ty);
    while(x>10||y>10){
        if(x<y)
            swap(x,y);
        x-=2;y-=1;
        x=abs(x);
        y=abs(y);
        ans++;
    }
    cout<<ans+bfs(x,y)<<endl;
    return 0;
}