Submission #1001656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001656		vjudge1	Robots (APIO13_robots)	C++17	30 / 100	1 ms	604 KiB

robots

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>


using namespace std;

#define int long long
#define len(x) (int)x.size()
#define all(x) (x).begin() , (x).end()
#define Bekabot ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define pb push_back
#define pii pair<int , int>
#define F first
#define S second
#define fopen(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)

const int N = 1e5 + 78 , M = 1e9 + 7 , inf = 1e18;
int n , w , h;
char a[505][505];
int dp[15][15][15];
int tmp = 1;
bool used[15][15];
int rev(int x){
	if(x == 1)x = 3;
	else if(x == 3)x = 2;
	else if(x == 2)x = 4;
	else if(x == 4)x = 1;
	return x;
}
int inv(int x){
	if(x == 1)x = 4;
	else if(x == 4)x = 2;
	else if(x == 2)x = 3;
	else if(x == 3)x = 1;
	return x;
}
void dfs(int x , int y , int p = 0){
	used[x][y] = 1;
	//if(tmp == 2)cout << x << ' ' << y << '\n';
	if(p != 1){
		int y1 = y , x1 = x;
		int cur = 1;
		while(1){
			if(a[x][y] == 'A'){
				cur = rev(cur);
			}
			else if(a[x][y] == 'C'){
				cur = inv(cur);
			}
			if(cur == 1){
				if(a[x][y + 1] == 'x' or y + 1 > w)break;
				y++;
			}
			else if(cur == 2){
				if(a[x][y - 1] == 'x' or y - 1 == 0)break;
				y--;
			}
			else if(cur == 3){
				if(a[x - 1][y] == 'x' or x - 1 == 0)break;
				x--;
			}
			else if(cur == 4){
				if(a[x + 1][y] == 'x' or x + 1 > h)break;
				x++;
			}
		}
		dp[tmp][x][y] = min(dp[tmp][x][y] , dp[tmp][x1][y1] + 1);
		if(!used[x][y])dfs(x , y , cur);
		y = y1 , x = x1;
	}
	if(p != 2){
		int y1 = y , x1 = x , cur = 2;
		while(1){
			if(a[x][y] == 'A'){
				cur = rev(cur);
			}
			else if(a[x][y] == 'C'){
				cur = inv(cur);
			}
			if(cur == 1){
				if(a[x][y + 1] == 'x' or y + 1 > w)break;
				y++;
			}
			else if(cur == 2){
				if(a[x][y - 1] == 'x' or y - 1 == 0)break;
				y--;
			}
			else if(cur == 3){
				if(a[x - 1][y] == 'x' or x - 1 == 0)break;
				x--;
			}
			else if(cur == 4){
				if(a[x + 1][y] == 'x' or x + 1 > h)break;
				x++;
			}
		}
		dp[tmp][x][y] = min(dp[tmp][x][y] , dp[tmp][x1][y1] + 1);
		if(!used[x][y])dfs(x , y , cur);
		y = y1 , x = x1;	
	}
	if(p != 3){
		int x1 = x , y1 = y , cur = 3;
		while(1){
			if(a[x][y] == 'A'){
				cur = rev(cur);
			}
			else if(a[x][y] == 'C'){
				cur = inv(cur);
			}
			if(cur == 1){
				if(a[x][y + 1] == 'x' or y + 1 > w)break;
				y++;
			}
			else if(cur == 2){
				if(a[x][y - 1] == 'x' or y - 1 == 0)break;
				y--;
			}
			else if(cur == 3){
				if(a[x - 1][y] == 'x' or x - 1 == 0)break;
				x--;
			}
			else if(cur == 4){
				if(a[x + 1][y] == 'x' or x + 1 > h)break;
				x++;
			}
		}
		dp[tmp][x][y] = min(dp[tmp][x][y] , dp[tmp][x1][y1] + 1);
		if(!used[x][y])dfs(x , y , cur);
		x = x1 , y1 = y;			
	}
	if(p != 4){
		int x1 = x , y1 = y , cur = 4;
		while(1){
			if(a[x][y] == 'A'){
				cur = rev(cur);
			}
			else if(a[x][y] == 'C'){
				cur = inv(cur);
			}
			if(cur == 1){
				if(a[x][y + 1] == 'x' or y + 1 > w)break;
				y++;
			}
			else if(cur == 2){
				if(a[x][y - 1] == 'x' or y - 1 == 0)break;
				y--;
			}
			else if(cur == 3){
				if(a[x - 1][y] == 'x' or x - 1 == 0)break;
				x--;
			}
			else if(cur == 4){
				if(a[x + 1][y] == 'x' or x + 1 > h)break;
				x++;
			}
		}
		dp[tmp][x][y] = min(dp[tmp][x][y] , dp[tmp][x1][y1] + 1);
		if(!used[x][y])dfs(x , y , cur);
		x = x1 , y = y1;		
	}
}
//1 >
//2 <
//3 ^
//4 v
void skibidi_dop_dop_dop_yes_yes(){
	cin >> n >> w >> h;
	vector<pii> v;
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= w ; j++){
			cin >> a[i][j];
			dp[1][i][j] = dp[2][i][j] = inf;
			if(a[i][j] >= '1' and a[i][j] <= '9')v.pb({i , j});
		}
	}
	for(auto it : v){
		dp[tmp][it.F][it.S] = 0;
		dfs(it.F , it.S);
		tmp++;
		for(int i = 1 ; i <= h ; i++)for(int j = 1 ; j <= w ; j++)used[i][j] = 0;
		//break;
	}
	int mn = inf;
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= w ; j++){
			mn = min(mn , dp[1][i][j] + dp[2][i][j]);
			//cout << dp[2][i][j] << ' ';
		}
		//cout << '\n';
	}
	if(mn < inf)cout << mn;
	else cout << -1;
	
}

signed main(){
	int t = 1;
	Bekabot
	while(t--)skibidi_dop_dop_dop_yes_yes();
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40