Submission #1002499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002499		vjudge1	Robots (APIO13_robots)	C++17	100 / 100	1234 ms	108664 KiB

robots

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


using namespace std;

#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 = 1e9;

int h , w , n;
int ans[10][10][505][505];
int dp[505][505];
int dx[] = {1 , 0 , -1 , 0} , dy[] = {0 , 1 , 0 , -1};
char a[505][505];
vector<pii> g[505][505];
pii id[10];
pii s[505][505][5];
bool p(int x , int y){
	if(1 <= x and x <= h and 1 <= y and y <= w and a[x][y] != 'x')return 1;
	return 0;
}
pii fnd(int x , int y , int t){
	if(s[x][y][t].F and s[x][y][t].S)return s[x][y][t];
	s[x][y][t] = {-inf , -inf};
	int tt = t;
	if(a[x][y] == 'A'){
		tt = (tt + 1) % 4;
	}
	else if(a[x][y] == 'C'){
		tt = (tt + 3) % 4;
	}
	int x1 = x + dx[tt] , y1 = y + dy[tt];
	if(p(x1 , y1))return s[x][y][t] = fnd(x1 , y1 , tt);
	else return s[x][y][t] = {x , y};
}
void build(){
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= w ; j++){
			if(a[i][j] == 'x')continue;
			for(int t = 0 ; t <= 3 ; t++){
				pii aa = fnd(i , j , t);
				if(a[i][j] != 'x' and aa.F > 0)g[i][j].pb(aa);
			}
		}
	}
}
void skibidi_dop_dop_dop_yes_yes(){
	cin >> n >> w >> h;
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= w ; j++){
			cin >> a[i][j];
			if(a[i][j] >= '1' and a[i][j] <= '9')id[a[i][j] - '0'] = {i , j};
		}
	}
	build();
	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++){
					ans[l][r][i][j] = inf;
				}
			}
		}
	}
	for(int i = 1 ; i <= n ; i++){
		ans[i][i][id[i].F][id[i].S] = 0;
	}
	for(int ll = 1 ; ll <= n ; ll++){
		for(int l = 1 ; l + ll - 1 <= n ; l++){
			int r = l + ll - 1;
			set<pair<int , pii>> st;
			for(int i = 1 ; i <= h ; i++){
				for(int j = 1 ; j <= w ; j++){
					for(int md = l ; md < r ; md++){
						ans[l][r][i][j] = min(ans[l][r][i][j] , ans[l][md][i][j] + ans[md + 1][r][i][j]);
					}
					if(ans[l][r][i][j] != inf)st.insert({ans[l][r][i][j] , {i , j}});
				}
			}
			while(len(st)){
				auto v = *st.begin();
				st.erase(st.begin());
				for(auto it : g[v.S.F][v.S.S]){
					if(ans[l][r][it.F][it.S] > ans[l][r][v.S.F][v.S.S] + 1){
						st.erase({ans[l][r][it.F][it.S] , {it.F , it.S}});
						ans[l][r][it.F][it.S] = ans[l][r][v.S.F][v.S.S] + 1;
						st.insert({ans[l][r][it.F][it.S] , {it.F , it.S}});
					}
				}
			}
		}
	}
	int mx = inf;
	for(int i = 1 ; i <= h ; i++)for(int j = 1 ; j <= w ; j++)mx = min(mx , ans[1][n][i][j]);
	if(mx < inf)cout << mx;
	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: 30 / 30
• Subtask 4: 40 / 40