Submission #422093

#	Time	Username	Problem	Language	Result	Execution time	Memory
422093		rqi	Robots (APIO13_robots)	C++14	100 / 100	474 ms	128456 KiB

robots

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40