题目地址https://www.acwing.com/problem/content/description/2137/在国际象棋和中国象棋中马的移动规则相同都是走“日”字我们将这种移动方式称为马步移动。如下图所示从标号为0 00的点出发可以经过一步马步移动达到标号为1 11的点经过两步马步移动达到标号为2 22的点。任给平面上的两点p pp和s ss它们的坐标分别为( x p , y p ) (x_p,y_p)(xp,yp)和( x s , y s ) (x_s,y_s)(xs,ys)其中x p , y p , x s , y s x_p,y_p,x_s,y_sxp,yp,xs,ys均为整数。从( x p , y p ) (x_p,y_p)(xp,yp)出发经过一步马步移动可以达到( x p 1 , y p 2 ) , ( x p 2 , y p 1 ) , ( x p 1 , y p − 2 ) , ( x p 2 , y p − 1 ) , ( x p − 1 , y p 2 ) , ( x p − 2 , y p 1 ) , ( x p − 1 , y p − 2 ) , ( x p − 2 , y p − 1 ) (x_p1,y_p2),(x_p2,y_p1),(x_p1,y_p−2),(x_p2,y_p−1),(x_p−1,y_p2),(x_p−2,y_p1),(x_p−1,y_p−2),(x_p−2,y_p−1)(xp1,yp2),(xp2,yp1),(xp1,yp−2),(xp2,yp−1),(xp−1,yp2),(xp−2,yp1),(xp−1,yp−2),(xp−2,yp−1)。假设棋盘充分大并且坐标可以为负数。现在请你求出从点p pp到点s ss至少需要经过多少次马步移动输入格式只包含4 44个整数它们彼此用空格隔开分别为x p , y p , x s , y s x_p,y_p,x_s,y_sxp,yp,xs,ys。输出格式输出一个整数表示从点p pp到点s ss至少需要经过的马步移动次数。数据范围− 10 7 x p , y p , x s , y s 10 7 −10^7x_p,y_p,x_s,y_s10^7−107xp,yp,xs,ys107证明见https://blog.csdn.net/qq_46105170/article/details/105673059。代码如下#includeiostreamusingnamespacestd;longf(longx,longy){if(!x!y)return0;if(x1y0)return3;if(x2y2)return4;if(yx-y){if(x%20)returnx/2(x/2-y)%2;elsereturn(x1)/2((x1)/2-(y1))%2;}longd(2*y-x)/3;if(!d)d1;xd,y-d;returnf(x,y);}intmain(){longx,y,a,b;scanf(%ld%ld%ld%ld,x,y,a,b);longcabs(x-a),dabs(y-b);if(cd)swap(c,d);printf(%ld\n,abs(f(c,d)));return0;}时空复杂度O ( 1 ) O(1)O(1)。
