Description
Input
只包含4个整数,它们彼此用空格隔开,分别为xp,yp,xs,ys。并且它们的都小于10000000。
Output
含一个整数,表示从点p到点s至少需要经过的马步移动次数。
Sample Input
1 2 7 9
Sample Output
5
题解
这道题的解题思路是大范围贪心,小范围暴力。个人觉得这个东西在一些暴力骗分中很有用。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> #define mod 7005 using namespace std; int xs,ys,xt,yt,ans; int xx[8]={1,1,-1,-1,2,2,-2,-2},yy[8]={2,-2,2,-2,1,-1,1,-1}; int map[105][105],f[105][105],qx[10005],qy[10005]; void pre() { xt=abs(xt-xs); yt=abs(yt-ys); xs=0; ys=0; int x=0,y=0,dx,dy; while(abs(xt-x)+abs(yt-y)>50) {dx=abs(xt-x); dy=abs(yt-y); if(dx>2*dy) x+=4; else if(dy>2*dx) y+=4; else if(dx<=dy) {x+=2; y+=4;} else {x+=4; y+=2;} ans+=2; } xt=abs(xt-x); yt=abs(yt-y); xs+=50; ys+=50; xt+=50; yt+=50; } bool check(int x,int y) { if(x<0||y<0||x>100||y>100) return true; if(f[x][y]!=-1) return true; return false; } void work() { int t=0,w=1,xn,yn,xa,ya,i; memset(f,-1,sizeof(f)); qx[0]=xs; qy[0]=ys; f[xs][ys]=0; while(t!=w) {xn=qx[t]; yn=qy[t]; t=(t+1)%mod; for(i=0;i<8;i++) {xa=xn+xx[i]; ya=yn+yy[i]; if(check(xa,ya)) continue; f[xa][ya]=f[xn][yn]+1; qx[w]=xa; qy[w]=ya; w=(w+1)%mod; if(f[xt][yt]!=-1) return ; } } } int main() { freopen("horse.in","r",stdin); freopen("horse.out","w",stdout); scanf("%d%d%d%d",&xs,&ys,&xt,&yt); pre(); work(); printf("%d\n",ans+f[xt][yt]); return 0; }