oj.uz

Submission #422093

# Submission time Handle Problem Language Result Execution time Memory
422093 2021-06-09T17:27:49 Z rqi Robots (APIO13_robots) C++14
100 / 100
 474 ms 128456 KB 
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long long ll;
typedef vector<ll> vl;

#define pb push_back
#define bk back()
#define sz(x) (int)(x).size()
#define f first
#define s second
#define mp make_pair

void ckmin(int& a, int b){
	a = min(a, b);
}

const int MOD = 1e9+7;

vi dx = vi{1, 0, -1, 0};
vi dy = vi{0, 1, 0, -1};

const int mx = 505;
int n, w, h;
bool wall[mx][mx];
pi adj[mx][mx][4]; //-3 is unknown, -2 is in progress, -1 is bad
pi initial_pos[10];
int dir[mx][mx];

void genTrans(int X, int Y, int d){
	if(adj[X][Y][d] != mp(-3, -3)) return;
	if(wall[X+dx[d]][Y+dy[d]]){
		adj[X][Y][d] = mp(X, Y);
		return;
	}
	adj[X][Y][d] = mp(-2, -2);
	int new_X = X+dx[d];
	int new_Y = Y+dy[d];
	int new_d = (d+dir[new_X][new_Y]+4) % 4;
	if(adj[new_X][new_Y][new_d] == mp(-2, -2)){
		adj[X][Y][d] = mp(-1, -1);
		return;
	}
	genTrans(new_X, new_Y, new_d);
	adj[X][Y][d] = adj[new_X][new_Y][new_d];
}

int dist[10][10][mx][mx];
vpi dist_poses[mx*mx];

void PRINT(pi& a){
	cout << "(" << a.f << ", " << a.s << ")" << "\n";
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> w >> h;

	for(int i = 1; i <= h; i++){
		string s;
		cin >> s;
		for(int j = 1; j <= w; j++){
			if(s[j-1] == 'x'){
				wall[i][j] = 1;
			}
			else if('1' <= s[j-1] && s[j-1] <= '9'){
				initial_pos[s[j-1]-'0'] = mp(i, j);
			}
			else if(s[j-1] == 'A'){
				dir[i][j] = 1;
			}
			else if(s[j-1] == 'C'){
				dir[i][j] = -1;
			}
		}
	}

	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			for(int d = 0; d < 4; d++){
				adj[i][j][d] = mp(-3, -3);
			}
		}
	}

	for(int i = 0; i <= h+1; i++){
		wall[i][0] = wall[i][w+1] = 1;
	}

	for(int i = 0; i <= w+1; i++){
		wall[0][i] = wall[h+1][i] = 1;
	}

	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			if(wall[i][j]) continue;
			for(int d = 0; d < 4; d++){
				genTrans(i, j, d);
			}
		}
	}




	for(int L = 1; L <= n; L++){
		for(int R = 1; R <= n; R++){
			for(int i = 1; i <= h; i++){
				for(int j = 1; j <= w; j++){
					if(wall[i][j]) continue;
					dist[L][R][i][j] = MOD;
				}
			}
		}
	}

	for(int L = 1; L <= n; L++){
		dist[L][L][initial_pos[L].f][initial_pos[L].s] = 0;
	}

	// for(int i = 1; i <= h; i++){
	// 	for(int j = 1; j <= w; j++){
	// 		for(int d = 0; d < 4; d++){
	// 			if(adj[i][j][d] != mp(-1, -1)){
	// 				cout << i << " " << j << " " << d << " " << adj[i][j][d].f << " " << adj[i][j][d].s << "\n";
	// 			}
	// 		}
	// 	}
	// }


	for(int SZ = 0; SZ <= n-1; SZ++){
		for(int L = 1; L+SZ <= n; L++){
			int R = L+SZ;

			
			for(int MID = L; MID+1 <= R; MID++){
				for(int i = 1; i <= h; i++){
					for(int j = 1; j <= w; j++){
						if(wall[i][j]) continue;
						ckmin(dist[L][R][i][j], dist[L][MID][i][j]+dist[MID+1][R][i][j]);
					}
				}
			}
			
			priority_queue<pair<int, pi>, vector<pair<int, pi>>, greater<pair<int, pi>>> pq; //distance, position
			for(int i = 1; i <= h; i++){
				for(int j = 1; j <= w; j++){
					if(wall[i][j]) continue;
					if(dist[L][R][i][j] != MOD){
						dist_poses[dist[L][R][i][j]].pb(mp(i, j));
						//pq.push(mp(dist[L][R][i][j], mp(i, j)));
					}
				}
			}

			for(int DIST = 0; DIST < mx*mx; DIST++){
				while(sz(dist_poses[DIST])){
					pi pos = dist_poses[DIST].bk; dist_poses[DIST].pop_back();
					if(dist[L][R][pos.f][pos.s] != DIST) continue;

					for(int d = 0; d < 4; d++){
						if(adj[pos.f][pos.s][d] == mp(-1, -1)) continue;
						pi new_pos = adj[pos.f][pos.s][d];

						if(dist[L][R][new_pos.f][new_pos.s] <= DIST+1) continue;
						dist[L][R][new_pos.f][new_pos.s] = DIST+1;
						dist_poses[DIST+1].pb(new_pos);
					}
				}
			}
			
		}
	}
	
	// cout << dist[3][3][1][7] << "\n";
	// cout << dist[4][4][1][7] << "\n";
	// cout << dist[3][4][1][7] << "\n";

	int ans = MOD;
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			if(wall[i][j]) continue;
			ckmin(ans, dist[1][n][i][j]);
		}
	}

	if(ans == MOD){
		cout << -1 << "\n";
	}
	else{
		cout << ans << "\n";
	}

	

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6348 KB Output is correct
2 Correct 5 ms 6348 KB Output is correct
3 Correct 5 ms 6348 KB Output is correct
4 Correct 5 ms 6476 KB Output is correct
5 Correct 5 ms 6348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6348 KB Output is correct
2 Correct 5 ms 6348 KB Output is correct
3 Correct 5 ms 6348 KB Output is correct
4 Correct 5 ms 6476 KB Output is correct
5 Correct 5 ms 6348 KB Output is correct
6 Correct 6 ms 6476 KB Output is correct
7 Correct 5 ms 6348 KB Output is correct
8 Correct 6 ms 6348 KB Output is correct
9 Correct 5 ms 6316 KB Output is correct
10 Correct 5 ms 6432 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6348 KB Output is correct
2 Correct 5 ms 6348 KB Output is correct
3 Correct 5 ms 6348 KB Output is correct
4 Correct 5 ms 6476 KB Output is correct
5 Correct 5 ms 6348 KB Output is correct
6 Correct 6 ms 6476 KB Output is correct
7 Correct 5 ms 6348 KB Output is correct
8 Correct 6 ms 6348 KB Output is correct
9 Correct 5 ms 6316 KB Output is correct
10 Correct 5 ms 6432 KB Output is correct
11 Correct 110 ms 62400 KB Output is correct
12 Correct 12 ms 11556 KB Output is correct
13 Correct 56 ms 40032 KB Output is correct
14 Correct 187 ms 68160 KB Output is correct
15 Correct 95 ms 59716 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6348 KB Output is correct
2 Correct 5 ms 6348 KB Output is correct
3 Correct 5 ms 6348 KB Output is correct
4 Correct 5 ms 6476 KB Output is correct
5 Correct 5 ms 6348 KB Output is correct
6 Correct 6 ms 6476 KB Output is correct
7 Correct 5 ms 6348 KB Output is correct
8 Correct 6 ms 6348 KB Output is correct
9 Correct 5 ms 6316 KB Output is correct
10 Correct 5 ms 6432 KB Output is correct
11 Correct 110 ms 62400 KB Output is correct
12 Correct 12 ms 11556 KB Output is correct
13 Correct 56 ms 40032 KB Output is correct
14 Correct 187 ms 68160 KB Output is correct
15 Correct 95 ms 59716 KB Output is correct
16 Correct 175 ms 95404 KB Output is correct
17 Correct 474 ms 128456 KB Output is correct
18 Correct 174 ms 99204 KB Output is correct
19 Correct 139 ms 95228 KB Output is correct
20 Correct 303 ms 110116 KB Output is correct