Submission #1001900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001900		vjudge1	Robots (APIO13_robots)	C++17	30 / 100	42 ms	16220 KiB

robots

/*
	Dimash ne katai!!!
	shnurok krash))
	Serikbay777 tozhe krash))
*/
#include <bits/stdc++.h>
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define Respaabs1equal2xdoner ios_base::sync_with_stdio(0);cin.tie(0);
#define pll pair < long long , long long >
#define all(x) x.begin() , x.end()
#define pii pair < int , int >
#define	pofik continue
#define int long long
#define pb push_back
#define ins insert
#define sz size()
#define F first
#define S second
const long long N = 300 + 77 , inf = 1e18 + 77 , MOD = 1e9 + 7;
const long double eps = 1e-11;
using namespace std;
int T = 1;
int binpow(int a , int b){
	if(!b) return 1;
	int val = binpow(a , b / 2);
	if(b % 2 == 0) return val * val % MOD;
	else return val * val * a % MOD;
}
/*
	1.........
	AA.x4.....
	..A..x....
	2....x....
	..C.3.A...
*/

set < pll > g[N][N];
int dst[N][N];

bool is_digit(char c){
	if('0' <= c && c <= '9') return 1;
	return 0;
}

void solve(){
	int n , h , w;
	cin >> n >> h >> w;
	swap(h , w);
	char c[h + 1][w + 1];
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			cin >> c[i][j];
			dst[i][j] = inf;
		}
	}
	queue < pll > t;
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			if(c[i][j] == 'x') pofik;
			map < pair < pll , int > , int > mp;
			int cur , x , y;
			bool ok;
			cur = 1;
			x = i , y = j;
			ok = 1;
			while(ok){
				if(mp[{{x , y} , cur}]) x = h + 1 , y = w + 1;
				if(mp[{{x , y} , cur}]) break;
				mp[{{x , y} , cur}] = 1;
				if(c[x][y] == 'A') cur = (cur - 1 + 4) % 4;
				if(c[x][y] == 'C') cur = (cur + 1) % 4;
				if(cur == 0){
					if(x == 1 || (x > 1 && c[x - 1][y] == 'x')) break;
					x--;
				}
				if(cur == 1){
					if(y == w || (y < w && c[x][y + 1] == 'x')) break;
					y++;
				}
				if(cur == 2){
					if(x == h || (x < h && c[x + 1][y] == 'x')) break;
					x++;
				}
				if(cur == 3){
					if(y == 1 || (y > 1 && c[x][y - 1] == 'x')) break;
					y--;
				}
			}
			if(x != h + 1){
				if(is_digit(c[i][j])) t.push({x , y});
				g[x][y].ins({i , j});
			}
			mp.clear();
			cur = 2;
			x = i , y = j;
			ok = 1;
			while(ok){
				if(mp[{{x , y} , cur}]) x = h + 1 , y = w + 1;
				if(mp[{{x , y} , cur}]) break;
				mp[{{x , y} , cur}] = 1;
				if(c[x][y] == 'A') cur = (cur - 1 + 4) % 4;
				if(c[x][y] == 'C') cur = (cur + 1) % 4;
				if(cur == 0){
					if(x == 1 || (x > 1 && c[x - 1][y] == 'x')) break;
					x--;
				}
				if(cur == 1){
					if(y == w || (y < w && c[x][y + 1] == 'x')) break;
					y++;
				}
				if(cur == 2){
					if(x == h || (x < h && c[x + 1][y] == 'x')) break;
					x++;
				}
				if(cur == 3){
					if(y == 1 || (y > 1 && c[x][y - 1] == 'x')) break;
					y--;
				}
			}
			if(x != h + 1){
				if(is_digit(c[i][j])) t.push({x , y});
				g[x][y].ins({i , j});
			}
			mp.clear();
			cur = 3;
			x = i , y = j;
			ok = 1;
			while(ok){
				if(mp[{{x , y} , cur}]) x = h + 1 , y = w + 1;
				if(mp[{{x , y} , cur}]) break;
				mp[{{x , y} , cur}] = 1;
				if(c[x][y] == 'A') cur = (cur - 1 + 4) % 4;
				if(c[x][y] == 'C') cur = (cur + 1) % 4;
				if(cur == 0){
					if(x == 1 || (x > 1 && c[x - 1][y] == 'x')) break;
					x--;
				}
				if(cur == 1){
					if(y == w || (y < w && c[x][y + 1] == 'x')) break;
					y++;
				}
				if(cur == 2){
					if(x == h || (x < h && c[x + 1][y] == 'x')) break;
					x++;
				}
				if(cur == 3){
					if(y == 1 || (y > 1 && c[x][y - 1] == 'x')) break;
					y--;
				}
			}
			if(x != h + 1){
				if(is_digit(c[i][j])) t.push({x , y});
				g[x][y].ins({i , j});
			}
			mp.clear();
			cur = 0;
			x = i , y = j;
			ok = 1;
			while(ok){
				if(mp[{{x , y} , cur}]) x = h + 1 , y = w + 1;
				if(mp[{{x , y} , cur}]) break;
				mp[{{x , y} , cur}] = 1;
				if(c[x][y] == 'A') cur = (cur - 1 + 4) % 4;
				if(c[x][y] == 'C') cur = (cur + 1) % 4;
				if(cur == 0){
					if(x == 1 || (x > 1 && c[x - 1][y] == 'x')) break;
					x--;
				}
				if(cur == 1){
					if(y == w || (y < w && c[x][y + 1] == 'x')) break;
					y++;
				}
				if(cur == 2){
					if(x == h || (x < h && c[x + 1][y] == 'x')) break;
					x++;
				}
				if(cur == 3){
					if(y == 1 || (y > 1 && c[x][y - 1] == 'x')) break;
					y--;
				}
			}
			if(x != h + 1){
				if(is_digit(c[i][j])) t.push({x , y});
				g[x][y].ins({i , j});
			}
		}
	}
	int ans = inf;
	while(t.sz){
		pll x = t.front();
		t.pop();
		dst[x.F][x.S] = 0;
		queue < pll > q;
		q.push(x);
		while(q.sz){
			pll v = q.front();
			q.pop();
			for(pll to : g[v.F][v.S]){
				if(dst[to.F][to.S] > dst[v.F][v.S] + 1){
					dst[to.F][to.S] = dst[v.F][v.S] + 1;
					q.push(to);
				}
			}
		}
		int sum = 0;
		for(int i = 1; i <= h; i++){
			for(int j = 1; j <= w; j++){
				if(is_digit(c[i][j])) sum += dst[i][j];
				// if(x.F == 1 && x.S == 1){
					// cout << dst[i][j] << ' ';
				// }
				dst[i][j] = inf;
			}
			// cout << '\n';
		}
		ans = min(ans , sum);
		// cout << x.F << ' ' << x.S << ' ' << sum << '\n';
	}
	if(ans == inf) cout << -1;
	else cout << ans;
	// for(int i = 1; i <= h; i++){
		// for(int j = 1; j <= w; j++){
			// cout << i << ' ' << j << ":\n";
			// for(pll to : g[i][j]){
				// cout << to.F << ' ' << to.S << '\n';
			// }
			// cout << '\n';
		// }
	// }
}

signed main(){
    Respaabs1equal2xdoner
	// cin >> T;
    for(int cas = 1; cas <= T; cas++){
    	// cout << "Case " << cas << ":\n";
    	solve();
    }
}

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