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) {
| ^
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
