제출 #1121488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121488		resolve100	로봇 (APIO13_robots)	C++14	0 / 100	1 ms	336 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
#pragma GCC optimize ("Ofast")

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][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(){
	scanf("%d%d%d", &n, &w, &h);
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			scanf("%c", &mat[i][j]);	
		}
	}

	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>, vector<vector<int>>, decltype(&pro)> q1(&pro);
			// 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});
				}
			}



			// transfer it. ie got it from somewhere else
			bool vis[h][w]; memset(vis, 0, sizeof(vis));
			while(!q1.empty()){
				auto 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;
						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) printf("-1\n");
	else printf("%d\n", ans);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

robots.cpp: In function 'int32_t main()':
robots.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d%d%d", &n, &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:61:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |    scanf("%c", &mat[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

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