我看到的题解都是贪心+打表，理论上应该是O(n)的吧。

昨天的比赛有一道题，题目跟这个一样，但是数据范围大了很多，所以就想问一下这题有没有严格证明的O(1)做法。下面是我写的代码，本题可以AC，但是不会证明正确性。

#include <bits/stdc++.h> 
using namespace std;
int a,b,c,d,mk[105][105],mov[8][2]={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
int Abs(int x){
	if(x<0)return -x;
	return x;
}
struct node{
	int x,y,cs;
};
queue<node>q;
void BFS(){
	q.push((node){a,b,0});
	while(q.size()){
		node cc=q.front();
		mk[cc.x][cc.y]=1;
		q.pop();
		if(cc.x==c&&cc.y==d){
			cout<<cc.cs;
			return;
		} 
		for(int i=0;i<8;i++){
			int xx=cc.x+mov[i][0],yy=cc.y+mov[i][1];
			if(xx<=100&&yy<=100&&xx>=0&&yy>=0){
				if(mk[xx][yy])continue;
				mk[xx][yy]=1;
				q.push((node){xx,yy,cc.cs+1});
			}
		}
	} 
}
int main(){
	cin>>a>>b>>c>>d;
	int xx=Abs(c-a),yy=Abs(d-b);
	if(xx<=10&&yy<=10){
		a=10,b=10,c=a+xx,d=b+yy;
		BFS(); 
		return 0;
	}
	if(xx>2*yy||yy>2*xx){
		if(xx>yy)swap(xx,yy);
		yy-=2*xx;
		if(yy%2==0&&(yy/2)%2==0)cout<<xx+yy/2;
		else if(yy%2&&(yy/2)%2)cout<<xx+yy/2+2;
		else cout<<xx+yy/2+1; 
		return 0;
	}
	int k=Abs(2*xx-yy);
	if(k%3!=1)cout<<xx-k/3;
	else cout<<xx-k/3+1;
}