Labyrintti

#include <bits/stdc++.h>

#define i64 long long
#define u64 unsigned long long
#define i32 int
#define u32 unsigned int

#define pii pair<int, int>
#define pll pair<long long, long long>

#define defmod 1000000007
using namespace std;


int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	int y1, x1, y2, x2;
	cin >> y1 >> x1 >> y2 >> x2;
	y1*=-1;
	y2*=-1;
	unordered_map<int, unordered_map<int, int> > lol;
	lol[0][0] = 0;
	int x = 0, y = 0;
	for(int i = 1; i <= 16; i++){
		if(i%4 == 1){
			for(int j = x; j <= x+(1<<i); j++)
				lol[y][j] = 0;
			x+=(1<<i);
		}
		else if(i%4 == 2){
			for(int j = y; j <= y+(1<<i); j++)
				lol[j][x] = 0;
			y+=(1<<i);
		}
		else if(i%4 == 3){
			for(int j = x; j >= x-(1<<i); j--)
				lol[y][j] = 0;
			x-=(1<<i);
		}
		else{
			for(int j = y; j >= y-(1<<i); j--)
				lol[j][x] = 0;
			y-=(1<<i);
		}
		//cout << x << ", " << y << endl;
	}
	queue<pair<int, pii> > q;
	q.push({0, {y1, x1}});
	while(!q.empty()){
		int cx = q.front().second.second;
		int cy = q.front().second.first;
		int dist = q.front().first;
		q.pop();
		if(lol[cy].count(cx))
			continue;
		//cout << "nyt " << cx << ", " << cy << endl;
		lol[cy][cx] = dist;
		if(cx == x2 && cy == y2){
			cout << dist << endl;
			return 0;
		}
		q.push({dist+1, {cy+1, cx}});
		q.push({dist+1, {cy-1, cx}});
		q.push({dist+1, {cy, cx+1}});
		q.push({dist+1, {cy, cx-1}});
	}
	return 0;
}

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: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED