#include <bits/stdc++.h>
using namespace std;
const int dx[4] = { 0, 1, 0, -1 };
const int dy[4] = { -1, 0, 1, 0 };
const int INF = 0x3f3f3f3f;
int n, w, h, go[1515151], ho[1515151], a[1515151];
int dist[505][505], dp[9][9][505][505], g[505][505];
string S[505];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> w >> h;
for (int i = 0; i < h; i++) {
cin >> S[i];
}
for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
int x = w * i + j;
int y[4] = {};
for (int k = 0; k < 4; k++) {
int ni = i + dx[k];
int nj = j + dy[k];
if (ni < 0 || nj < 0 || ni >= h || nj >= w || S[ni][nj] == '#') {
y[k] = -1;
}
else y[k] = w * ni + nj;
}
go[5 * x] = 5 * x;
for (int k = 0; k < 4; k++) {
if (S[i][j] == 'A') {
if (y[(k + 1) % 4] == -1) {
go[5 * x + 1 + k] = 5 * x;
}
else go[5 * x + 1 + k] = 5 * y[(k + 1) % 4] + 1 + (k + 1) % 4;
}
else if (S[i][j] == 'C') {
if (y[(k + 3) % 4] == -1) {
go[5 * x + 1 + k] = 5 * x;
}
else go[5 * x + 1 + k] = 5 * y[(k + 3) % 4] + 1 + (k + 3) % 4;
}
else if (S[i][j] != '#') {
if (y[k] == -1) {
go[5 * x + 1 + k] = 5 * x;
}
else go[5 * x + 1 + k] = 5 * y[k] + 1 + k;
}
}
}
for (int k = 0; k < 30; k++) {
for (int i = 0; i < 5 * w * h; i++) {
ho[i] = go[go[i]];
}
for (int i = 0; i < 5 * w * h; i++) {
go[i] = ho[i];
}
}
if (n == 2) {
queue<pair<int, int>> Q, R;
for (int x = 0; x < h; x++) for (int y = 0; y < w; y++) {
if (S[x][y] == '1') Q.emplace(0, w * x + y);
if (S[x][y] == '2') R.emplace(0, w * x + y);
}
memset(dist, 0x3f, sizeof dist);
while (!Q.empty()) {
auto [d, v] = Q.front(); Q.pop();
if (dist[v / w][v % w] != INF) continue;
dist[v / w][v % w] = d;
for (int i = 1; i <= 4; i++) {
Q.emplace(d + 1, go[5 * v + i] / 5);
}
}
memset(g, 0x3f, sizeof g);
while (!R.empty()) {
auto [d, v] = R.front(); R.pop();
if (g[v / w][v % w] != INF) continue;
g[v / w][v % w] = d;
for (int i = 1; i <= 4; i++) {
R.emplace(d + 1, go[5 * v + i] / 5);
}
}
int ans = INF;
for (int x = 0; x < h; x++) for (int y = 0; y < w; y++) {
ans = min(ans, dist[x][y] + g[x][y]);
}
cout << (ans == INF ? -1 : ans) << '\n';
return 0;
}
iota(a, a + w * h, 0);
for (int d = 0; d < n; d++) for (int i = 0; i < n - d; i++) {
int j = i + d;
for (int x = 0; x < h; x++) for (int y = 0; y < w; y++) {
g[x][y] = INF;
if (d == 0) {
g[x][y] = (S[x][y] - '1' == i) ? 0 : INF;
}
else {
for (int k = i; k < j; k++) {
g[x][y] = min(g[x][y], dp[i][k][x][y] + dp[k + 1][j][x][y]);
}
}
}
memset(dist, 0x3f, sizeof dist);
sort(a, a + w * h, [&](int i, int j) {
return g[i / w][i % w] < g[j / w][j % w];
});
queue<pair<int, int>> Q, R;
for (int i = 0; i < w * h; i++) {
if (g[a[i] / w][a[i] % w] != INF) {
Q.emplace(5 * a[i], g[a[i] / w][a[i] % w]);
}
else break;
}
while (!Q.empty() || !R.empty()) {
int v, d;
if (Q.empty() || (!R.empty() && Q.front().second >= R.front().second)) {
tie(v, d) = R.front(); R.pop();
}
else {
tie(v, d) = Q.front(); Q.pop();
}
// cout << i << ' ' << j << ' ' << "(" << (v / 5 / w) << ", " << (v / 5 % w) << ") " << ' ' << d << '\n';
assert(v % 5 == 0);
if (dist[v / 5 / w][v / 5 % w] != INF) continue;
dist[v / 5 / w][v / 5 % w] = d;
for (int k = 1; k <= 4; k++) {
if (go[v + k] % 5 != 0) continue;
R.emplace(go[v + k], d + 1);
}
}
for (int x = 0; x < h; x++) for (int y = 0; y < w; y++) {
dp[i][j][x][y] = dist[x][y];
}
}
int ans = INF;
for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
ans = min(ans, dp[0][n - 1][i][j]);
}
cout << (ans == INF ? -1 : ans);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
