제출 #1121587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121587		resolve100	Robots (APIO13_robots)	C++14	30 / 100	125 ms	72704 KiB

robots

#include <bits/stdc++.h>
#define pb push_back
// #define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define f first
#define s second
#define endl '\n'
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define read_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

// template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// __builtin_popcount() 1s cnt
// __builtin_clz() 0s left
// __builtin_ctz(x) 0s right

const int N=9, M=500;
int dp[M][M][N][N];

pair<int, int> rep[M][M][4];
bool vis[M][M][4];
// char* mat[M];
vector<string> mat(M);

// 0 up, 1 right, 2 down, 3 left
vector<pair<int, int>> dx={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
 
int n, w, h;
bool bad(int i, int j){
	return (i<0||j<0||i>=h||j>=w||mat[i][j]=='x');
}
 
pair<int, int> dfs(int i, int j, int dir){
	if(bad(i, j)) return {i-dx[dir].f, j-dx[dir].s};
	if(vis[i][j][dir]) return rep[i][j][dir];
 
	vis[i][j][dir]=true;
	int dir2=dir;
 
	if(mat[i][j]=='C') dir2=(dir2+1)%4;
	if(mat[i][j]=='A') dir2=(dir2-1+4)%4;
 
	return rep[i][j][dir]=dfs(i+dx[dir2].f, j+dx[dir2].s, dir2);
}
 
bool pro(vector<int>& v1, vector<int>& v2){
	return v1[0]>=v2[0];
}
 
 
int32_t main(){
    cin>>n>>w>>h;
	for(int i=0; i<h; i++){
        cin>>mat[i];
	}

	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			for(int k=0; k<4; k++) {
				vis[i][j][k]=false;
				rep[i][j][k]={-1, -1};
			}
 
			for(int l=0; l<N; l++){
				for(int r=0; r<N; r++){
					dp[i][j][l][r]=1e9;
				}
			}
		}
	}
 
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			int ch=mat[i][j]-'1';
			if(ch>=0&&ch<n){
				dp[i][j][ch][ch]=0;
			}
 
			for(int k=0; k<4; k++){
				if(vis[i][j][k]) continue;
				dfs(i, j, k);
			}
		}
	}
	for(int len=1; len<=n; len++){
		for(int k=0; k+len<=n; k++){
			int l=k, r=k+len-1;

            vector<vector<int>> q1;
			// build robot. ie got it from me	
			for(int i=0; i<h; i++){
				for(int j=0; j<w; j++){
					for(int z=k+1; z<=r; z++){
						dp[i][j][l][r]=min(dp[i][j][l][r], dp[i][j][l][z-1]+dp[i][j][z][r]);
					}
 
					if(dp[i][j][l][r]!=1e9) q1.push_back({-dp[i][j][l][r], i, j});
				}
			}
            sort(q1.begin(), q1.end(), pro);
 
            queue<vector<int>> q2;
			// transfer it. ie got it from somewhere else
			bool vis[h][w]; memset(vis, 0, sizeof(vis));
			while(!q1.empty()||!q2.empty()){
                vector<int> curr;
                if(q1.empty()||(!q2.empty()&&(q2.front()[0]<=q1.back()[0]))) {curr=q2.front(); q2.pop();}
				else {curr=q1.back(); q1.pop_back();}
 
				if(vis[curr[1]][curr[2]]) continue;
				vis[curr[1]][curr[2]]=true;
 
				for(int dir=0; dir<4; dir++){
					pair<int, int> next=rep[curr[1]][curr[2]][dir];
					if(!bad(next.f, next.s)&&dp[next.f][next.s][l][r]>dp[curr[1]][curr[2]][l][r]+1){
						dp[next.f][next.s][l][r]=dp[curr[1]][curr[2]][l][r]+1;
						q2.push({-dp[next.f][next.s][l][r], next.f, next.s});
					}
				}
			}
		}
	}
 
	int ans=1e9;
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			ans=min(ans, dp[i][j][0][n-1]);
		}
	}
 
	if(ans==1e9) printf("-1\n");
	else printf("%d\n", ans);
	return 0;
}

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