[BZOJ1193][HNOI2006]马步距离大范围贪心小范围爆搜

2023-08-25 20:48:28

1193: [HNOI2006]马步距离

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1988 Solved: 905
[Submit][Status][Discuss]

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

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int tx[]={,,,,-,-,-,-};

 int ty[]={,,-,-,,,-,-};

 int xp,yp,xs,ys;

 int dis[][];

 int q1[],q2[];

 int bfs(int x,int y) {

     memset(dis,-,sizeof(dis));

     int s=,t=;

     q1[s]=x;q2[s]=y;

     dis[x][y]=;

     while(s!=t) {

         int nx=q1[s++],ny=q2[s-];if(s==) s=;

         for(int i=;i<;i++) {

             int tox=nx+tx[i],toy=ny+ty[i];

             if(tox<||toy<||tox>||toy>||dis[tox][toy]!=-) continue;

             dis[tox][toy]=dis[nx][ny]+;

             q1[t]=tox,q2[t++]=toy;if(t==) t=;

         }

     }

     return dis[][];

 }

 int main() {

     scanf("%d%d%d%d",&xp,&yp,&xs,&ys);

     int x=abs(xp-xs),y=abs(yp-ys);

     int cnt=;

     while(x+y>=) {

         if(x<y) swap(x,y);

         if(x->=y*) x-=;

         else x-=,y-=;

         cnt+=;

     }

     x+=,y+=;

     printf("%d",cnt+bfs(x,y));

     return ;

 }