主播主播 @ ，你的注意力确实惊人，但是 $O(1)$ 结论还是太吃操作了，有没有思路清晰，而且实现简单的做法呢？

有的兄弟，有的

这里是一篇线性题解

注意到数据是1e7，显然就不能bfs了。但是不难发现，我们离 $goal$ 非常远的时候，并不需要跳的太仔细，只要每一步大体方向都是冲着 $goal$ 去的，那么一定是不劣的（瞎**乱跳也是没问题的）

还会注意到：先走一个 $(1,2)$ 再走一个 $(2,1)$ 就可以走出一个 $3*3$ 对角线的方向。

所以说：

仅当我们与 $goal$ 的相对位置在 $3*3$ 以内时，我们才要认真考虑此时怎么走

⁡ 直接手磨：

由于对角线两侧情况一样，这里只处理一侧

可以看到(2,2)并没有直接写。

手磨发现是4

但是！

真的是4吗？

黑是由红走过来的

但是如果直接从红走到goal快了整整2步

所以说finalstep的优先级是：

1. 处理(3,4)
2. 处理(3,3)以内
3. 乱跳

这样我们的finalstep就处理完了，上代码：

int a,b,c,d;
int ans;
int finalstep[4][4]={{0,3,2,3},{3,2,1,2},{2,1,4,3},{3,2,3,2}};
inline void solve(){
	reads(a);
	reads(b);
	reads(c);
	reads(d);
	c=abs(c-a);
	d=abs(d-b);
	a=b=0;
	for(;;ans++){
		if((abs(a-c)==3&&abs(b-d)==4)||(abs(a-c)==4&&abs(b-d)==3)){
			ans+=3;
			break;
		}
		if(abs(a-c)<=3&&abs(b-d)<=3){
			ans+=finalstep[abs(a-c)][abs(b-d)];
			break;
		}
		else if(abs(a-c)>=abs(b-d)){
			if(c>a)a+=2;
			else a-=2;
			if(d>b)b++;
			else b--;
		}
		else{
			if(c>a)a++;
			else a--;
			if(d>b)b+=2;
			else b-=2;
		}
//		cout<<"("<<a<<","<<b<<")"<<endl;
	}
	cout<<ans;
}

PS:可以考虑把问题转化为第一象限内从原点出发的问题，避免了一些问题

这篇题解并不长，但是为了不被贴上“短而空”的标签，我决定放一下bfs代码：

int dx[]= {1,2,2,1,-1,-2,-2,-1};
int dy[]= {2,1,-1,-2,-2,-1,1,2};
queue<pair<int,int> >q;
int vis[1005][1005];
void bfs(){
  q.push({100,100});
	x+=100,y+=100;
	while(!q.empty()) {
		pair<int,int> u=q.front();
		q.pop();
		for(int i=0; i<8; ++i) {
			int xx=u.first+dx[i],yy=u.second+dy[i];
			if(vis[xx][yy])continue;
			vis[xx][yy]=vis[u.first][u.second]+1;
			if(xx==x&&yy==y) {
				cout<<vis[xx][yy]<<"\n";
				return ;
//				exit(0) ;
			}
			q.push({xx,yy});
		}
	}
}

这个bfs可能是全篇唯一没什么价值的东西了qwq

主播主播 @ ，你的思路确实清晰，但是线性做法还是太吃操作了，有没有代码好写，又跑得飞快的 $O(1)$ 做法呢？

有的兄弟，有的

这里是一篇 $O(1)$ 题解

这篇题解非常的长，而且前面的内容也许没什么用。但是贡献一个bfs（在最后），这样大家就可以对拍了。

注意到数据是1e7，显然不能bfs了。但是发现，起点和重点的绝对坐标不是很重要，所以：

cin>>ccF>>CCf>>x>>y;
x-=ccF,y-=CCf,x=abs(x),y=abs(y);
if(x>y)swap(x,y);

然后是bfs，这里就不给出代码了。

显然40分还不够多，我们决定打表。

打表思路

y=0 ---> y=x ---> y=x+1 ---> y=x+2

(y-x)%3=0 ---> (y-x)%3=1 ---> (y-x)%3=2

表大概长这样 y=x:

0 0 :2
1 1 :2
2 2 :4
3 3 :2
4 4 :4
5 5 :4
6 6 :4
7 7 :6
8 8 :6
9 9 :6
10 10 :8
11 11 :8
12 12 :8
13 13 :10
14 14 :10
15 15 :10
16 16 :12
17 17 :12
18 18 :12
19 19 :14
20 20 :14

y=x+1:

0 1 :3
1 2 :1
2 3 :3
3 4 :3
4 5 :3
5 6 :5
6 7 :5
7 8 :5
8 9 :7
9 10 :7
10 11 :7
11 12 :9
12 13 :9
13 14 :9
14 15 :11
15 16 :11
16 17 :11
17 18 :13
18 19 :13
19 20 :13
20 21 :15

y=x+2:

0 2 :2
1 3 :2
2 4 :2
3 5 :4
4 6 :4
5 7 :4
6 8 :6
7 9 :6
8 10 :6
9 11 :8
10 12 :8
11 13 :8
12 14 :10
13 15 :10
14 16 :10
15 17 :12
16 18 :12
17 19 :12
18 20 :14
19 21 :14
20 22 :14

y=x+4

0 4 :2
1 5 :4
2 6 :4
3 7 :4
4 8 :4
5 9 :6
6 10 :6
7 11 :6
8 12 :8
9 13 :8
10 14 :8
11 15 :10
12 16 :10
13 17 :10
14 18 :12
15 19 :12
16 20 :12
17 21 :14
18 22 :14
19 23 :14
20 24 :16

看y=x，y=x+1,y=x+2，

再对比y=x+1,y=x+4，我们注意到：

if(x==0) {
	if(y%4==0)cout<<y/2;
	else if(y%4==1)cout<<y/2+1;
	else if(y%4==2)cout<<y/2+1;
	else if(y%4==3)cout<<y/2+2;
} 
else if((y-x)%3==1) {
	if(x%3!=2) cout<<(y-x)/3+x/3*2+1;
	else cout<<(y-x)/3+(x+1)/3*2+1;
} else if((y-x)%3==2) {
	cout<<(y-x)/3+x/3*2+2;
} else {
	cout<<(y-x)/3+(x+2)/3*2;
}

但是，发现这样大样例过不去。

我们开始思考问题的本质

为什么是y=x+4一开始是有4个一组，有4个连续的4，后面又变成3个一组？

继续打表：

y=x+7

0 7 :5
1 8 :5
2 9 :5
3 10 :5
4 11 :7
5 12 :7
6 13 :7
7 14 :7
8 15 :9
9 16 :9
10 17 :9
11 18 :11
12 19 :11
13 20 :11
14 21 :13
15 22 :13
16 23 :13
17 24 :15
18 25 :15
19 26 :15
20 27 :17

前边有两组4个的，后面又都成三个了，所以应该分类讨论，y>2x和y<=2x的情况。

这是因为y<=2x时一开始没法乱跳，y>2x时一开始可以一直往上跳。

这篇题解非常的长，为了使它更有价值，我决定放一下bfs代码：

完整代码如下

#include<bits/stdc++.h>
#define int long long
using namespace std;
int ccF,CCf,x,y;
int dx[]= {1,2,2,1,-1,-2,-2,-1};
int dy[]= {2,1,-1,-2,-2,-1,1,2};
queue<pair<int,int> >q;
int vis[1005][1005];
void bfs();
signed main() {
	cin>>ccF>>CCf>>x>>y;
	x-=ccF,y-=CCf,x=abs(x),y=abs(y);
	if(x>y)swap(x,y);
	if(x<=20&&y<=20) bfs();
	if(y>=2*x) {
		if((y-x)&1) {
			if(y>=2*x) {
				if(y%4==2)cout<<y/2<<"\n";
				else if(y%4==1)cout<<y/2+1<<"\n";
				else if(y%4==0)cout<<y/2+1<<"\n";
				else cout<<y/2+2<<"\n";
			} else cout<<(y-x)/3+(x+2)/3*2<<"\n";
		} else {
			if(y>=2*x) cout<<(y+3)/4*4/2<<"\n";
			else cout<<(y-x)/3+(x+2)/3*2<<"\n";
		}
	} else if(x==0) {
		if(y%4==0)cout<<y/2<<"\n";
		else if(y%4==1)cout<<y/2+1;
		else if(y%4==2)cout<<y/2+1;
		else if(y%4==3)cout<<y/2+2;
	} else if(y==(x<<1))cout<<min(x,y)<<"\n";
	else if((y-x)%3==1) {
		if(x%3!=2) cout<<(y-x)/3+x/3*2+1<<"\n";
		else cout<<(y-x)/3+(x+1)/3*2+1<<"\n";
	} else if((y-x)%3==2) cout<<(y-x)/3+x/3*2+2<<"\n";
	else if((y-x)%3==0) cout<<(y-x)/3+(x+2)/3*2<<"\n";
	return 0;
}
void bfs() {
	q.push({100,100});
	x+=100,y+=100;
	while(!q.empty()) {
		pair<int,int> u=q.front();
		q.pop();
		for(int i=0; i<8; ++i) {
			int xx=u.first+dx[i],yy=u.second+dy[i];
			if(vis[xx][yy])continue;
			vis[xx][yy]=vis[u.first][u.second]+1;
			if(xx==x&&yy==y) {
				cout<<vis[xx][yy]<<"\n";
				exit(0) ;
			}
			q.push({xx,yy});
		}
	}
}

这个bfs可能是全篇唯一有点价值的东西了qwq

主播主播，你们的线性和 $O(1)$ 做法还是太吃操作了，有没有什么看上去不那么乱搞的做法？

有的兄弟，有的

我们注意到马的八种跳法本质上只有四种，中心对称的做法都可以归为一类。

我们分别设四种走法为 $a$ ，$b$ ，$c$ , $d$。

然后我们可以得到方程：

$a+d+2b+2c=t_1$ $2a-2d+b-c=t_2$

然后我们消元得到：

$4a+5b+3c=2*t_1+t_2$

然后我们就可以愉快地枚举 $a$ 和 $b$ 了。

注意到当 $a$ 固定时，答案随着 $b$ 是单谷的。

然后我们枚举 $a+$ 三分

复杂度 $O(nlogn)$

然后喜提暴力哥同分

代码：

#include<bits/stdc++.h>
using namespace std;
int t1,t2,up;
inline int calcc(int a,int b){
	int c=2*t1+t2-4*a-5*b;
	c/=3;
	int d=t1-a-2*b-2*c;
	return abs(a)+abs(b)+abs(c)+abs(d);
}inline int solve(int a){
	int delt=(2*t1+t2-4*a)%3+3;
	delt%=3;
	delt=2*delt%3;
	int l=-2*up/3,r=2*up/3;
	int cnt=0;
	while(l<=r){
		int midl=l+(r-l)/3,midr=r-(r-l)/3;
		if(calcc(a,midl*3+delt)>calcc(a,midr*3+delt))l=midl+1;
		else r=midr-1;
	}return min(calcc(a,l*3+delt),calcc(a,r*3+delt));
}
int main(){
	int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	t1=x2-x1,t2=y2-y1;
	int ans=1000000000;
	up=max(abs(t1),abs(t2));
	up=min(up,300000);
//	cout<<solve(up/10)<<endl;
	for(int a=-2*up; a<=2*up ;a++){
		ans=min(ans,solve(a));
	}cout<<ans;
	return 0;
}

大范围贪心，小范围暴搜。

应该可以将贪心过程优化到 $\Theta(1)$，但我懒得想了。

#include <bits/stdc++.h>
using namespace std;

int bfs(int x, int y) {
  queue<pair<pair<int, int>, int> > q;
  q.push(make_pair(make_pair(0, 0), 0));
  while (!q.empty()) {
    auto tp = q.front();
    q.pop();
    if (tp.first.first == x && tp.first.second == y) return tp.second;
    q.push(make_pair(make_pair(tp.first.first + 1, tp.first.second + 2),
                     tp.second + 1));
    q.push(make_pair(make_pair(tp.first.first + 2, tp.first.second + 1),
                     tp.second + 1));
    q.push(make_pair(make_pair(tp.first.first + 2, tp.first.second - 1),
                     tp.second + 1));
    q.push(make_pair(make_pair(tp.first.first + 1, tp.first.second - 2),
                     tp.second + 1));
    q.push(make_pair(make_pair(tp.first.first - 1, tp.first.second - 2),
                     tp.second + 1));
    q.push(make_pair(make_pair(tp.first.first - 2, tp.first.second - 1),
                     tp.second + 1));
    q.push(make_pair(make_pair(tp.first.first - 2, tp.first.second + 1),
                     tp.second + 1));
    q.push(make_pair(make_pair(tp.first.first - 1, tp.first.second + 2),
                     tp.second + 1));
  }
  return INT32_MAX;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int a, b, c, d, cnt = 0;
  cin >> a >> b >> c >> d;
  int x = abs(a - c), y = abs(b - d);
  while (x >= 4 || y >= 4) {
    if (x < 0) x = -x;
    if (y < 0) y = -y;
    if (x < y) swap(x, y);
    x -= 2, y -= 1; ++cnt;
  }
  cout << bfs(x, y) + cnt;
  return 0;
}