제출 #552417

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
552417		QwertyPi	로봇 (APIO13_robots)	C++14	100 / 100	927 ms	143652 KiB

robots

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 501, MAXM = 501, MAXD = 9;
const int INF = (1 << 25);
char board[MAXN][MAXM];
int dp[MAXN][MAXM][MAXD][MAXD];
int dd[MAXN][MAXM];
pii f[MAXN][MAXM][4];
pii pos[MAXD];
 
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
 
int d, n, m;
bool in(int i, int j){
	return 0 <= i && i < n && 0 <= j && j < m && board[i][j] != 'x';
}
 
bool vis[MAXN][MAXM][4];
inline pii dfs(int i, int j, int dir){
	if(vis[i][j][dir]) return {-1, -1};
	if(f[i][j][dir].fi != -2) return f[i][j][dir];
	vis[i][j][dir] = true;
	if(!in(i + dx[dir], j + dy[dir])){
		f[i][j][dir] = {i, j};
		vis[i][j][dir] = false;
		return {i, j};
	}
	f[i][j][dir] = dfs(i + dx[dir], j + dy[dir], (dir + dd[i + dx[dir]][j + dy[dir]] + 4) % 4);
	vis[i][j][dir] = false;
	return f[i][j][dir];
}
 
struct CMP{
	bool operator()(pair<pii, pii> a, pair<pii, pii> b){
		return a.fi.fi > b.fi.fi;
	}
};
 
vector<pair<int, pii>> q[MAXN * MAXM];
int main(){
	cin >> d >> m >> n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> board[i][j];
			if(board[i][j] >= '0' && board[i][j] <= '9') pos[board[i][j] - '1'] = {i, j}, board[i][j] = '.';
			if(board[i][j] == 'C') dd[i][j] = 1;
			if(board[i][j] == 'A') dd[i][j] = -1;
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int dir = 0; dir < 4; dir++){
				f[i][j][dir].fi = -2;
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int dir = 0; dir < 4; dir++){
				if(f[i][j][dir].fi == -2) dfs(i, j, dir);
			}
		}
	}
//	for(int i = 0; i < n; i++){
//		for(int j = 0; j < m; j++){
//			for(int k = 0; k < 4; k++){
//				cout << i << ' ' << j << ' ' << k << ' ' << f[i][j][k].fi << ' ' << f[i][j][k].se << endl;
//			}
//		}
//	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int d1 = 0; d1 < d; d1++){
				for(int d2 = d1; d2 < d; d2++){
					dp[i][j][d1][d2] = INF;
				}
			}
		}
	}

	for(int i = 0; i < d; i++){
		for(int x = 0; x < n; x++){
			for(int y = 0; y < m; y++){
				for(int dl = 0; dl < i - 1; dl++){
					for(int dm = dl; dm < i - 1; dm++){
						dp[x][y][dl][i] = min(dp[x][y][dl][i], dp[x][y][dl][dm] + dp[x][y][dm + 1][i]);
					}
				}
			}
		}
		for(int j = i; j >= 1; j--){
			int c = dp[pos[i].fi][pos[i].se][j - 1][i - 1];
			if(c >= INF) continue;
			dp[pos[i].fi][pos[i].se][j - 1][i] = c;
		}
		dp[pos[i].fi][pos[i].se][i][i] = 0;
		for(int q0 = i; q0 >= 0; q0--){
			for(int x = 0; x < n; x++) for(int y = 0; y < m; y++) if(dp[x][y][q0][i] < INF) q[dp[x][y][q0][i]].push_back({q0, {x, y}});
			for(int k = 0; k <= n * m; k++){
				while(!q[k].empty()){
					pair<int, pii> v = q[k].back(); q[k].pop_back();
					int nd = v.fi, x = v.se.fi, y = v.se.se;
					for(int dir = 0; dir < 4; dir++){
						int nx = f[x][y][dir].fi, ny = f[x][y][dir].se;
						if(nx == x && ny == y) continue;
						int co = k + 1;
						if(co >= dp[nx][ny][nd][i]) continue;
						dp[nx][ny][nd][i] = co;
						q[co].push_back({nd, {nx, ny}});
						for(int j = nd; j >= 1; j--){
							if(co + dp[nx][ny][j - 1][nd - 1] >= dp[nx][ny][j - 1][i]) continue;
							dp[nx][ny][j - 1][i] = co + dp[nx][ny][j - 1][nd - 1];
						}
					}
				}
			}
		}
	}
	
	int ans = INF;
//	for(int d1 = 0; d1 < d; d1++){
//		for(int d2 = d1; d2 < d; d2++){
//			cout << "d " << d1 << ' ' << d2 << endl;
//			for(int i = 0; i < n; i++){
//				for(int j = 0; j < m; j++){
//					cout << (dp[i][j][d1][d2] >= INF ? -1 : dp[i][j][d1][d2]) << ' ';
//				}
//				cout << endl;
//			}
//		}
//	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			ans = min(ans, dp[i][j][0][d - 1]);
		}
	}
	cout << (ans >= INF ? -1 : ans) << endl;
}

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