Labyrintti

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

vector<pair<pair<ll, ll>, pair<ll, ll> > > wa;
ll d[111][111];

int bw(ll p1, ll p2, ll p){
	if (p1<=p&&p<=p2) return 1;
	if (p2<=p&&p<=p1) return 1;
	return 0;
}

ll can(ll x1, ll y1, ll x2, ll y2){
	if (x1>x2) swap(x1, x2);
	if (y1>y2) swap(y1, y2);
	for (auto w:wa){
		int xv=0;
		int yv=0;
		if (bw(w.F.F, w.S.F, x1)) xv=1;
		if (bw(w.F.F, w.S.F, x2)) xv=1;
		if (bw(x1, x2, w.F.F)) xv=1;
		if (bw(x1, x2, w.S.F)) xv=1;
		
		if (bw(w.F.S, w.S.S, y1)) yv=1;
		if (bw(w.F.S, w.S.S, y2)) yv=1;
		if (bw(y1, y2, w.F.S)) yv=1;
		if (bw(y1, y2, w.S.S)) yv=1;
		
		if (xv&&yv) return 0;
	}
	return 1;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tx=0;
	ll ty=0;
	ll k=2;
	int di=0;
	vector<ll> xc;
	vector<ll> yc;
	while (k<(ll)1e17){
		ll nx=tx;
		ll ny=ty;
		if (di==0){
			nx=tx+k;
		}
		else if(di==1){
			ny=ty-k;
		}
		else if(di==2){
			nx=tx-k;
		}
		else if(di==3){
			ny=ty+k;
		}
		wa.push_back({{tx, ty}, {nx, ny}});
		xc.push_back(tx);
		xc.push_back(tx-1);
		xc.push_back(tx+1);
		yc.push_back(ty);
		yc.push_back(ty-1);
		yc.push_back(ty+1);
		k*=2;
		di++;
		di%=4;
		tx=nx;
		ty=ny;
	}
	ll y1,x1,y2,x2;
	cin>>y1>>x1>>y2>>x2;
	xc.push_back(x1);
	xc.push_back(x2);
	yc.push_back(y1);
	yc.push_back(y2);
	sort(xc.begin(), xc.end());
	xc.erase(unique(xc.begin(), xc.end()), xc.end());
	sort(yc.begin(), yc.end());
	yc.erase(unique(yc.begin(), yc.end()), yc.end());
	
	int gx=0;
	int gy=0;
	
	priority_queue<pair<ll, pair<int, int> > > dij;
	for (int i=0;i<(int)xc.size();i++){
		for (int ii=0;ii<(int)yc.size();ii++){
			if (xc[i]==x1&&yc[ii]==y1){
				dij.push({-1, {i, ii}});
			}
			if (xc[i]==x2&&yc[ii]==y2){
				gx=i;
				gy=ii;
			}
		}
	}
	while (!dij.empty()){
		auto x=dij.top();
		dij.pop();
		if (d[x.S.F][x.S.S]) continue;
		d[x.S.F][x.S.S]=-x.F;
		if (x.S.F==gx&&x.S.S==gy){
			cout<<-x.F-1<<endl;
			return 0;
		}
		for (int i=0;i<(int)xc.size();i++){
			if (i!=x.S.F){
				if (can(xc[x.S.F], yc[x.S.S], xc[i], yc[x.S.S])){
					dij.push({x.F-abs(xc[x.S.F]-xc[i]), {i, x.S.S}});
				}
			}
		}
		
		for (int i=0;i<(int)yc.size();i++){
			if (i!=x.S.S){
				if (can(xc[x.S.F], yc[x.S.S], xc[x.S.F], yc[i])){
					dij.push({x.F-abs(yc[x.S.S]-yc[i]), {x.S.F, i}});
				}
			}
		}
	}
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED