oj.uz

답안 #500705

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500705 2021-12-31T20:26:59 Z CodeTiger927 로봇 (APIO13_robots) C++14
0 / 100
 31 ms 81228 KB 
using namespace std;

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

#define MAXN 505
#define INF 1e6

int N,M,K,dp[9][9][MAXN][MAXN];
pair<int,int> to[MAXN][MAXN][4];
char g[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
vector<pair<pair<int,int>,int>> order;

pair<int,int> dfs(int a,int b,int c) {
	if(to[a][b][c].first != 0) return to[a][b][c];
	to[a][b][c] = {a,b};
	if(a <= 0 || a > N || b <= 0 || b > M || g[a][b] == 'x') {
		return to[a][b][c] = {-1,-1};
	}else if(g[a][b] == '.') {
		to[a][b][c] = dfs(a + dx[c],b + dy[c],c);
	}else if(g[a][b] == 'C') {
		int uwu = (c + 1) % 4;
		to[a][b][c] = dfs(a + dx[uwu],b + dy[uwu],uwu);
	}else{
		int uwu = (c + 3) % 4;
		to[a][b][c] = dfs(a + dx[uwu],b + dy[uwu],uwu);
	}
	if(to[a][b][c].first == -1) to[a][b][c] = {a,b};
	order.push_back({{a,b},c});
	return to[a][b][c];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> K >> M >> N;
	memset(dp,-1,sizeof(dp));
	for(int i = 1;i <= N;++i) {
		for(int j = 1;j <= M;++j) {
			cin >> g[i][j];
			if(g[i][j] - '1' < K && g[i][j] - '1' >= 0) {
				int uwu = g[i][j] - '1';
				dp[uwu][uwu][i][j] = 0;
				// cout << uwu << " " << i << " " << j << endl;
				g[i][j] = '.';
				vis[i][j] = true;
			}
		}
	}
	for(int i = 1;i <= N;++i) {
		for(int j = 1;j <= M;++j) {
			for(int k = 0;k < 4;++k) {
				dfs(i,j,k);
			}
		}
	}
	reverse(order.begin(),order.end());
	for(int k = 0;k < K;++k) {
		for(int i = 0;i < K - k;++i) {
			// cout << dp[0][1][1][1] << endl;
			int j = i + k;
			// cout << i << " " << j << endl;
			for(int a = 1;a <= N;++a) {
				for(int b = 1;b <= M;++b) {
					if(dp[i][j][a][b] == -1) dp[i][j][a][b] = INF;
					if(g[a][b] == 'x' || !vis[a][b]) continue;
					for(int l = i;l < j;++l) {
						dp[i][j][a][b] = min(dp[i][j][a][b],dp[i][l][a][b] + dp[l + 1][j][a][b]);
					}
				}
			}
			for(auto [a,b] : order) {
				int x = a.first;
				int y = a.second;
				if(!vis[x][y]) continue;
				int w = to[x][y][b].first;
				int z = to[x][y][b].second;
				// if(i == 1 && j == 1 && w == 2 && z == 1) cout << i << " " << j << " " << b << " " << x << " " << y << " " << w << " " << z << endl;
				// cout << b << endl;
				dp[i][j][w][z] = min(dp[i][j][w][z],dp[i][j][x][y] + 1);
				vis[w][z] = true;
			}
		}
	}
	int ans = INF;
	for(int i = 1;i <= N;++i) {
		for(int j = 1;j <= M;++j) {
			ans = min(ans,dp[0][K - 1][i][j]);
		}
	}
	// cout << to[4][1][3].first << " " << to[4][1][3].second << endl;
	// cout << dp[0][1][1][1] << endl;
	cout << (ans >= INF ? -1 : ans) << endl;
	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:77:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |    for(auto [a,b] : order) {
      |             ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 81100 KB Output is correct
2 Correct 31 ms 81072 KB Output is correct
3 Correct 29 ms 81180 KB Output is correct
4 Incorrect 30 ms 81228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 81100 KB Output is correct
2 Correct 31 ms 81072 KB Output is correct
3 Correct 29 ms 81180 KB Output is correct
4 Incorrect 30 ms 81228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 81100 KB Output is correct
2 Correct 31 ms 81072 KB Output is correct
3 Correct 29 ms 81180 KB Output is correct
4 Incorrect 30 ms 81228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 81100 KB Output is correct
2 Correct 31 ms 81072 KB Output is correct
3 Correct 29 ms 81180 KB Output is correct
4 Incorrect 30 ms 81228 KB Output isn't correct
5 Halted 0 ms 0 KB -