#include <bits/stdc++.h>
#define max 500
#define maxn 505
#define sm 9
#define maxlog 20
#define INF 1000000010
#define mod 998244353
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout << "passed"<<endl;
//#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
//#pragma GCC target("avx2")
using namespace std;
char c[maxn][maxn];
int dp[maxn][maxn][sm][sm];
int state[maxn][maxn][4];
pair<int, int> stops[maxn][maxn][4];
int n, h, w;
void read() {
cin >> n >> w >> h;
h += 2;w += 2;
for (int i = 0; i < w; ++i)
c[0][i] = c[h - 1][i] = 'x';
for (int i = 0; i < h; ++i)
c[i][0] = c[i][w - 1] = 'x';
for (int i = 1; i < h - 1; ++i)
for (int j = 1; j < w - 1; ++j)
cin >> c[i][j];
for (int i = 0; i < h; ++i)
for (int j = 0; j < w; ++j)
for (int k = 0; k < n; ++k)
for (int l = 0; l < n; ++l)
dp[i][j][k][l] = INF;
}
int dirx[] = {0, 1, 0, -1};
int diry[] = {1, 0, -1, 0};
pair<int, int> dfs(int i, int j, int k) {
if (state[i][j][k] == 2)
return stops[i][j][k];
if (state[i][j][k] == 1)
return stops[i][j][k] = {i, j};
state[i][j][k] = 1;
int nk = k;
if (c[i][j] == 'A')
nk = (k + 3) % 4;
if (c[i][j] == 'C')
nk = (k + 1) % 4;
int ni = i + dirx[nk], nj = j + diry[nk];
if (c[ni][nj] == 'x') {
state[i][j][k] = 2;
return stops[i][j][k] = {i, j};
}
else {
stops[i][j][k] = dfs(ni, nj, nk);
if (state[ni][nj][nk] == 1)
stops[i][j][k] = {i, j};
else
state[i][j][k] = 2;
return stops[i][j][k];
}
}
void solve() {
for (int len = 0; len < n; ++len) {
for (int l = 0; l + len < n; ++l) {
const int r = l + len;
vector<vector<pair<int, int>>> v(maxn * maxn + 5);
if (len == 0) {
for (int i = 0; i < h; ++i)
for (int j = 0; j < w; ++j)
if (c[i][j] - '1' == l) {
dp[i][j][l][r] = 0;
v[0].push_back({i, j});
}
}
else {
for (int i = 0; i < h; ++i)
for (int j = 0; j < w; ++j) {
int minn = INF;
for (int k = l; k < r; ++k)
minn = min(minn, dp[i][j][l][k] + dp[i][j][k + 1][r]);
dp[i][j][l][r] = minn;
if (minn < maxn * maxn)
v[minn].push_back({i, j});
}
}
for (int d = 0; d < maxn * maxn; ++d)
for (pair <int, int> e : v[d])
for (int k = 0; k < 4; ++k) {
pair <int, int> nb = dfs(e.X, e.Y, k);
if (dp[nb.X][nb.Y][l][r] > d + 1) {
dp[nb.X][nb.Y][l][r] = d + 1;
v[d + 1].push_back({nb.X, nb.Y});
}
}
// if (l == 0 and r == 1) {
// cout << "c : " << l << " " << r << " " << dp[4][4][0][1] << "\n";
// exit(0);
// }
}
}
}
void print() {
int ans = INF;
for (int i = 0; i < h; ++i)
for (int j = 0; j < w; ++j)
ans = min(ans, dp[i][j][0][n - 1]);
if(ans == INF)
cout << -1 << endl;
else
cout << ans << endl;
}
int main() {
freopen ("input.txt", "r",stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// cout << (int)'x' << " " << (int)'1';
// return 0;
read();
solve();
print();
return 0;
}
Compilation message
robots.cpp: In function 'std::pair<int, int> dfs(int, int, int)':
robots.cpp:56:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
56 | if (c[i][j] == 'C')
| ^~
robots.cpp:59:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
59 | int ni = i + dirx[nk], nj = j + diry[nk];
| ^~~
robots.cpp: In function 'int main()':
robots.cpp:129:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | freopen ("input.txt", "r",stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
