首页 > 代码库 > bzoj1193 [HNOI2006]马步距离
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
正解：贪心+广搜。
这种无语题也是醉了。。
我们当两个点距离很远的时候我们可以直接贪心地移动起点，使得两点距离缩小到能够搜索的范围内。
然后再跑广搜，两次移动的距离和就是答案。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define inf (1<<30)14 #define il inline15 #define RG register16 #define ll long long17 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)18 19 using namespace std;20 21 const int d1[8]={1,2,1,2,-1,-2,-1,-2};22 const int d2[8]={2,1,-2,-1,2,1,-2,-1};23 24 int qx[10010],qy[10010],dis[110][110],vis[110][110],x,y,sx,sy,tx,ty,ans;25 26 il int gi(){27 RG int x=0,q=1; RG char ch=getchar();28 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();29 if (ch==‘-‘) q=-1,ch=getchar();30 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();31 return q*x;32 }33 34 il void bfs(){35 RG int h=0,t=1; qx[t]=x,qy[t]=y;36 while (h<t){37 RG int xx=qx[++h],yy=qy[h],XX,YY;38 for (RG int i=0;i<8;++i){39 XX=xx+d1[i],YY=yy+d2[i];40 if (XX<0 || XX>100 || YY<0 || YY>100 || vis[XX][YY]) continue;41 dis[XX][YY]=dis[xx][yy]+1,qx[++t]=XX,qy[t]=YY;42 vis[XX][YY]=1; if (XX==50 && YY==50) return;43 }44 }45 return;46 }47 48 il void work(){49 sx=gi(),sy=gi(),tx=gi(),ty=gi(),x=abs(sx-tx),y=abs(sy-ty);50 while (x+y>=50){51 if (x<y) swap(x,y); ans+=2;52 if (x-4>=2*y) x-=4; else x-=4,y-=2;53 }54 x+=50,y+=50,bfs(); printf("%d\n",ans+dis[50][50]); return;55 }56 57 int main(){58 File("horse");59 work();60 return 0;61 }
bzoj1193 [HNOI2006]马步距离
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。