#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define ii pair <int, int>
#define fi first
#define se second
using namespace std;
const int MAXN = 505;
const int INF = 250000;
int N, W, H, dp[MAXN][MAXN][10][10];
char a[MAXN][MAXN];
vector <ii> q[INF + 1];
ii end_pos[MAXN][MAXN][4];
inline bool inside(int x, int y) {
return (x > 0 && y > 0 && x <= H && y <= W && a[x][y] != 'x');
}
void Find_ending_points(void) {
FOR(i, 1, H) FOR(j, 1, W) if (a[i][j] != 'x') {
REP(k, 4) {
ii pos = {i, j};
int d = (k + (a[i][j] == 'A') * 3 + (a[i][j] == 'C')) % 4;
while (true) {
if (d == 0) {
if (inside(pos.first - 1, pos.second)) pos.first--;
else break;
} else if (d == 1) {
if (inside(pos.first, pos.second + 1)) pos.second++;
else break;
} else if (d == 2) {
if (inside(pos.first + 1, pos.second)) pos.first++;
else break;
} else {
if (inside(pos.first, pos.second - 1)) pos.second--;
else break;
}
if (~end_pos[pos.first][pos.second][d].first) {
pos = end_pos[pos.first][pos.second][d];
break;
}
if (a[pos.first][pos.second] == 'A') d = (d + 3) % 4;
if (a[pos.first][pos.second] == 'C') d = (d + 1) % 4;
}
end_pos[i][j][k] = pos;
}
}
}
void solve(void) {
memset(dp, 0x3f3f3f3f, sizeof dp);
cin >> N >> W >> H;
FOR(i, 1, H) FOR(j, 1, W) {
cin >> a[i][j];
if (a[i][j] >= '0' && a[i][j] <= '9') {
dp[i][j][a[i][j] - '0'][a[i][j] - '0'] = 0;
}
REP(k, 4) end_pos[i][j][k] = {-1, -1};
}
Find_ending_points();
REP(div, N) {
FOR(l, 1, N - div) {
int r = l + div;
FOR(i, 1, H) FOR(j, 1, W) if (a[i][j] != 'x')
for (int k = l; k < r; k++)
dp[i][j][l][r] = min(dp[i][j][l][r], dp[i][j][l][k]
+ dp[i][j][k + 1][r]);
}
FOR(l, 1, N - div) {
int r = l + div;
FOR(i, 1, H) FOR(j, 1, W) if (a[i][j] != 'x' && dp[i][j][l][r] <= INF)
q[dp[i][j][l][r]].emplace_back(i, j);
FOR(i, 0, INF) if (q[i].size()) {
for (auto tmp : q[i]) {
int x = tmp.fi, y = tmp.se;
if (dp[x][y][l][r] == i) {
REP(k, 4) {
int u = end_pos[x][y][k].first, v = end_pos[x][y][k].second;
if (dp[u][v][l][r] > dp[x][y][l][r] + 1) {
dp[u][v][l][r] = dp[x][y][l][r] + 1;
q[dp[u][v][l][r]].emplace_back(u, v);
}
}
}
}
q[i].clear();
}
}
}
int ans = INT_MAX;
FOR(i, 1, H) FOR(j, 1, W) ans = min(ans, dp[i][j][1][N]);
cout << ans;
}
signed main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//int T; cin >> T; while (T--)
solve();
cerr << "Time elapsed: " << TIME << " s.\n";
return (0 ^ 0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
105940 KB |
Output is correct |
| 2 |
Incorrect |
40 ms |
105900 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
105940 KB |
Output is correct |
| 2 |
Incorrect |
40 ms |
105900 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
105940 KB |
Output is correct |
| 2 |
Incorrect |
40 ms |
105900 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
105940 KB |
Output is correct |
| 2 |
Incorrect |
40 ms |
105900 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
