1193: [HNOI2006]马步距离
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 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
5
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<cmath> 6 #include<algorithm> 7 using namespace std; 8 int tx[10]={1,2,1,2,-1,-2,-1,-2}; 9 int ty[10]={2,1,-2,-1,2,1,-2,-1}; 10 int xp,yp,xs,ys; 11 int dis[105][105]; 12 int q1[1005],q2[1005]; 13 int bfs(int x,int y) { 14 memset(dis,-1,sizeof(dis)); 15 int s=0,t=1; 16 q1[s]=x;q2[s]=y; 17 dis[x][y]=0; 18 while(s!=t) { 19 int nx=q1[s++],ny=q2[s-1];if(s==1000) s=0; 20 for(int i=0;i<8;i++) { 21 int tox=nx+tx[i],toy=ny+ty[i]; 22 if(tox<0||toy<0||tox>60||toy>60||dis[tox][toy]!=-1) continue; 23 dis[tox][toy]=dis[nx][ny]+1; 24 q1[t]=tox,q2[t++]=toy;if(t==1000) t=0; 25 } 26 } 27 return dis[30][30]; 28 } 29 int main() { 30 scanf("%d%d%d%d",&xp,&yp,&xs,&ys); 31 int x=abs(xp-xs),y=abs(yp-ys); 32 int cnt=0; 33 while(x+y>=30) { 34 if(x<y) swap(x,y); 35 if(x-4>=y*2) x-=4; 36 else x-=4,y-=2; 37 cnt+=2; 38 } 39 x+=30,y+=30; 40 printf("%d",cnt+bfs(x,y)); 41 return 0; 42 }