제출 #1121759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121759		resolve100	로봇 (APIO13_robots)	C++17	100 / 100	1308 ms	100364 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];
char mat[M][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++){
        for(int j=0; j<w; j++) {
            cin>>mat[i][j];
        }
	}

    // for(int i=0; i<h; i++){
    //     printf("%s\n", 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;
 
            // priority_queue<vector<int>> q1;
            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({-dp[i][j][l][r], i, j});
					if(dp[i][j][l][r]!=1e9) q1.push_back({dp[i][j][l][r], i, j});
				}
			}
            // sort(q1.begin(), q1.end(), pro);
            sort(q1.rbegin(), q1.rend());
 
            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()<=q1.back())) {
                    curr=move(q2.front()); q2.pop();
                }
				else {
                    curr=move(q1.back()); q1.pop_back();
                }

                // vector<int> curr=q1.top(); q1.pop();
 
				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});
                        // q1.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) cout<<-1<<endl;
	else cout<<ans<<endl;

	return 0;
}

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