Submission #500704

# Submission time Handle Problem Language Result Execution time Memory
500704 2021-12-31T20:24:49 Z CodeTiger927 Robots (APIO13_robots) C++14
0 / 100
45 ms 81188 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] = {-1,-1};
	if(a <= 0 || a > N || b <= 0 || b > M || g[a][b] == 'x') {
		return to[a][b][c];
	}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) {
			vis[i][j] = true;
			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:78:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |    for(auto [a,b] : order) {
      |             ^
# Verdict Execution time Memory Grader output
1 Correct 45 ms 81096 KB Output is correct
2 Correct 29 ms 81140 KB Output is correct
3 Correct 29 ms 81188 KB Output is correct
4 Incorrect 30 ms 81164 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 45 ms 81096 KB Output is correct
2 Correct 29 ms 81140 KB Output is correct
3 Correct 29 ms 81188 KB Output is correct
4 Incorrect 30 ms 81164 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 45 ms 81096 KB Output is correct
2 Correct 29 ms 81140 KB Output is correct
3 Correct 29 ms 81188 KB Output is correct
4 Incorrect 30 ms 81164 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 45 ms 81096 KB Output is correct
2 Correct 29 ms 81140 KB Output is correct
3 Correct 29 ms 81188 KB Output is correct
4 Incorrect 30 ms 81164 KB Output isn't correct
5 Halted 0 ms 0 KB -