1285: [Hnoi2006]馬步距離

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?36??Solved:?16
[Submit][Status][Web Board]

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)。假設棋盤充分大，并且坐標可以為負數?，F在請你求出從點p到點s 至少需要經過多少次馬步移動？

Input

只包含4個整數，它們彼此用空格隔開，分別為xp,yp,xs,ys。并且它們的都小于10000000。

Output

含一個整數，表示從點p到點s至少需要經過的馬步移動次數。

Sample Input

1 2 7 9

Sample Output

5

HINT

Source

1 #include <bits/stdc++.h> 2 using namespace std; 3 int dx[8]={1,1,-1,-1,2,2,-2,-2}; 4 int dy[8]={2,-2,2,-2,1,-1,1,-1}; 5 int a,b,c,d,x,y,ans; 6 int px[100000]; 7 int py[100000]; 8 int h[30][30]; 9 bool v[30][30]; 10 11 void bfs() 12 { 13 int head,tail,xx,yy,x,y,i; 14 head=0; 15 tail=1; 16 px[1]=0; 17 py[1]=0; 18 memset(h,127,sizeof(h)); 19 h[0][0]=0; 20 while (head!=tail) 21 { 22 head++; 23 x=px[head]; 24 y=py[head]; 25 v[x][y]=false; 26 for (i=0;i<8;i++) 27 { 28 xx=x+dx[i]; 29 yy=y+dy[i]; 30 if (xx>-10 && xx<20 && yy>-10 && yy<20) 31 if (h[xx][yy]>h[x][y]+1) 32 { 33 h[xx][yy]=h[x][y]+1; 34 if (!v[xx][yy]) 35 { 36 tail++; 37 px[tail]=xx; 38 py[tail]=yy; 39 v[x][y]=true; 40 } 41 } 42 } 43 } 44 } 45 46 int main() 47 { 48 cin>>a>>b>>c>>d; 49 x=abs(a-c); 50 y=abs(b-d); 51 bfs(); 52 while (x>=10 || y>=10) 53 { 54 if (x>y) 55 { 56 x=x-2; 57 y=y-1; 58 } 59 else 60 { 61 x=x-1; 62 y=y-2; 63 } 64 ans++; 65 x=abs(x); 66 y=abs(y); 67 } 68 ans=ans+h[x][y]; 69 cout<<ans<<endl; 70 return 0; 71 } 馬步距離

?

轉載于:https://www.cnblogs.com/LHR-HY/p/6879026.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[Hnoi2006]马步距离的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。