「BZOJ1193」[HNOI2006] 马步距离
Description
Input
只包含4个整数，它们彼此用空格隔开，分别为xp,yp,xs,ys。并且它们的都小于10000000。
Output
含一个整数，表示从点p到点s至少需要经过的马步移动次数。
Sample Input
1 2 7 9
Sample Output
5
题解
大范围贪心，然后小范围暴力
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> #include<cmath> #include<map> #include<queue> #define mod 1000000007 #define inf 2000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int x,y,ans; int xp,yp,xs,ys; int xx[8]={1,1,-1,-1,2,2,-2,-2},yy[8]={2,-2,2,-2,1,-1,1,-1}; int dis[105][105]; int qx[10005],qy[10005]; void bfs() { memset(dis,-1,sizeof(dis)); int head=0,tail=1; qx[0]=x;qy[0]=y;dis[x][y]=0; while(head!=tail) { int x=qx[head],y=qy[head];head++; for(int k=0;k<8;k++) { int nowx=x+xx[k],nowy=y+yy[k]; if(nowx<0||nowy<0||nowx>100||nowy>100)continue; if(dis[nowx][nowy]!=-1)continue; dis[nowx][nowy]=dis[x][y]+1; qx[tail]=nowx;qy[tail]=nowy;tail++; if(nowx==50&&nowy==50)return; } } } int main() { xp=read();yp=read();xs=read();ys=read(); x=abs(xp-xs);y=abs(yp-ys); while(x+y>=50) { if(x<y)swap(x,y); if(x-4>=2*y)x-=4; else x-=4,y-=2; ans+=2; } x+=50;y+=50; bfs(); printf("%d\n",ans+dis[50][50]); return 0; } |
计数器 9850871
OI 课件=>
OI 课件=>
黄学长,可以解释一下OI大神都喜欢水B站,看萌妹子吗?
毕竟都是宅男
毕竟都是男的