这种题 一眼不可做的样子 给了10分bfs 不过我当时开了个map判边界 其实可以将坐标轴平移几个格子就行了 然后把输入的坐标全部都搞成正的 bfs即可。
对于y==0 推坐标的规律 把两部三部能走的奇怪的步伐给搞出来 用0,4跑然后特判一下即可。
对于x==y 这个用3,3跑 然后特判一下。
bf code：
正解：
假设x>=y>=0. 当x<=2y时 每一步最多走三步 定义一个冗余值 wi=3-dx-dy.
冗余值总和为 3*步数-x-y. 显然最小化冗余值即可。
显然一开始先用(2,1)走 若x为奇数则加一部(1,2)走到(x,y').
然后 通过将(2,1)替换成两个(1,2)使得 y-y'❤️.
当y-y'0时显然最小 当y-y'1.将(1,2)替换为(2,1)+(-1,2)或者将两个(2,1)替换为(1,2)(1,2)(2,-1).冗余值为2.(2,2)需要特判一下。
当y-y'==2 加上(2,1)(-2,1)即可 由于不存在冗余值为1,3的步所以这样做是最小的。
当x>2y时 定义每一步的冗余值为2-dx. 显然总和为 2*步数-x.
首先 先用(2,1)走到(2y,y).然后利用(2,1),(2,-1)走到(x',y)使得x-x'<4.
若 x-x'0说明此时最小 若x-x'1.将之前的(2,1)改成(1,2),(2,-1)即可。冗余值为1 显然是最小的 需要特盘(1,0).
x-x'2.加上(1,2)(1,-2)冗余值为2 显然是最小的 x-x'3 加上(2,1)(2,1)(-1,2)即可 显然也是最小的。
代码很玄学 这里不再探讨 。
const int MAXN=100005;
int T;
int a,b;
int main()
{
freopen("jump.in","r",stdin);
freopen("jump.out","w",stdout);
get(T);
while(T--)
{
get(a);get(b);
a=abs(a);b=abs(b);
if(a<b)swap(a,b);
if(a==2&&b==2){puts("4");continue;}
if(a==1&&b==0){puts("3");continue;}
int res=0;
if(a<=2*b)
{
int x=a,y=b;
put((x+y)/3+(x+y)%3);
}
else
{
int x=a,y=b;
put((x-2*y)/4*2+(x-2*y)%4+y);
}
}
return 0;
}