oj.uz

Submission #1001900

# Submission time Handle Problem Language Result Execution time Memory
1001900 2024-06-19T08:26:34 Z vjudge1 Robots (APIO13_robots) C++17
30 / 100
 42 ms 16220 KB 
/*
	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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7008 KB Output is correct
2 Correct 3 ms 6980 KB Output is correct
3 Correct 3 ms 7008 KB Output is correct
4 Correct 2 ms 7012 KB Output is correct
5 Correct 2 ms 7008 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7008 KB Output is correct
2 Correct 3 ms 6980 KB Output is correct
3 Correct 3 ms 7008 KB Output is correct
4 Correct 2 ms 7012 KB Output is correct
5 Correct 2 ms 7008 KB Output is correct
6 Correct 3 ms 7012 KB Output is correct
7 Correct 3 ms 7012 KB Output is correct
8 Correct 3 ms 7012 KB Output is correct
9 Correct 2 ms 7140 KB Output is correct
10 Correct 3 ms 7152 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7008 KB Output is correct
2 Correct 3 ms 6980 KB Output is correct
3 Correct 3 ms 7008 KB Output is correct
4 Correct 2 ms 7012 KB Output is correct
5 Correct 2 ms 7008 KB Output is correct
6 Correct 3 ms 7012 KB Output is correct
7 Correct 3 ms 7012 KB Output is correct
8 Correct 3 ms 7012 KB Output is correct
9 Correct 2 ms 7140 KB Output is correct
10 Correct 3 ms 7152 KB Output is correct
11 Incorrect 42 ms 16220 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7008 KB Output is correct
2 Correct 3 ms 6980 KB Output is correct
3 Correct 3 ms 7008 KB Output is correct
4 Correct 2 ms 7012 KB Output is correct
5 Correct 2 ms 7008 KB Output is correct
6 Correct 3 ms 7012 KB Output is correct
7 Correct 3 ms 7012 KB Output is correct
8 Correct 3 ms 7012 KB Output is correct
9 Correct 2 ms 7140 KB Output is correct
10 Correct 3 ms 7152 KB Output is correct
11 Incorrect 42 ms 16220 KB Output isn't correct
12 Halted 0 ms 0 KB -