# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1093944 | Trisanu_Das | Robots (APIO13_robots) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn = 300, mxk = 9, w = 4, mxz = mxn * mxn * w;
const int dx[w] = {1, 0, -1, 0}, dy[w] = {0, 1, 0, -1};
int n, m, k, z;
char a[mxn][mxn];
int b[mxz], d[mxz], dp[mxk][mxk][mxz];
vector<int> g[mxz], q[mxz];
int f(int x, int y, int e){ return x * m * w + y * w + e;}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> k >> m >> n;
z = n * m * w
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> a[i][j];
memset(dp, 0x3f, sizeof(dp));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++) if(a[i][j] != 'x')
for(int l = 0; l < w; l++){
int e = (l + (a[i][j] == 'A' ? 1 : a[i][j] == 'C' ? w - 1 : 0)) % w;
int x = i + dx[e], y = j + dy[e], u = f(i, j, l);
if(x >= 0 && y >= 0 && x < n && y < m && a[x][y] != 'x') g[u].push_back(f(x, y, e));
else{
b[u] = 1;
for(int p = 0; p < w; p++) if(l != p) g[u].push_back(f(i, j, p));
}
if(isdigit(a[i][j])){
int x = a[i][j] - '1';
dp[x][x][u] = 0;
}
}
for(int i = k - 1; ~i; i--)
for(int j = i; j < k; j++){
for(int l = 0; l < z; l++) q[l].clear();
for(int l = 0; l < z; l++){
d[l] = 0;
if(b[l]) for(int p = i; p < j; p++) dp[i][j][l] = min(dp[i][j][l], dp[i][p][l] + dp[p + 1][j][l]);
if(dp[i][j][l] < z) q[dp[i][j][l]].push_back(l);
}
for(int l = 0; l < z; l++)
while(!q[l].empty()){
int c = q[l].back();
q[l].pop_back();
if(d[c]) continue;
d[c] = 1;
for(int p : g[c]){
int x = l + (c / w != p / w && b[p]);
if(dp[i][j][p] > x) q[dp[i][j][p] = x].push_back(p);
}
}
}
int ret = *min_element(dp[0][k - 1], dp[0][k - 1] + z);
cout << (ret < z ? ret : -1) << '\n';
}