#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
const int nx[4] = {-1, 0, 1, 0}, ny[4] = {0, 1, 0, -1};
int N, W, H, D[10][10][505][505];
vector<array<int, 2>> Q[2250005];
array<int, 2> G[505][505][5];
char grid[505][505];
array<int, 2> dfs(int i, int j, int k) {
if(G[i][j][k][0] != -1)
return G[i][j][k];
int nxt = k;
if(grid[i][j] == 'C') nxt = (nxt + 1) % 4;
if(grid[i][j] == 'A') nxt = (nxt + 3) % 4;
int x = i + nx[nxt], y = j + ny[nxt];
if(x < 0 || y < 0 || x >= H || y >= W || grid[x][y] == 'X')
return G[i][j][k] = {i, j};
return G[i][j][k] = dfs(x, y, nxt);
}
void update(int i, int j, int x, int y, int d) {
if(D[i][j][x][y] > d && d < 2250005) {
D[i][j][x][y] = d; Q[d].push_back({x, y});
}
}
void solve(int i, int j) {
for(int l = 0; l < 2250005; l++) {
for(auto u : Q[l]) {
if(D[i][j][u[0]][u[1]] != l)
continue;
for(int k = 0; k < 4; k++) {
array<int, 2> arr = G[u[0]][u[1]][k];
update(i, j, arr[0], arr[1], l + 1);
}
}
Q[l].clear();
}
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> W >> H;
for(int l = 0; l < H; l++)
for(int i = 0; i < W; i++)
cin >> grid[l][i];
memset(G, -1, sizeof G);
for(int l = 0; l < W; l++)
for(int i = 0; i < W; i++) {
for(int j = 0; j < 4; j++)
dfs(l, i, j);
}
for(int l = 0; l < N; l++)
for(int i = 0; i < N; i++)
for(int x = 0; x < H; x++)
for(int y = 0; y < W; y++)
D[l][i][x][y] = 1e9 + 7;
for(int l = 0; l < N; l++) {
for(int i = l; ~i; i--) {
if(i < l) {
for(int x = 0; x < H; x++)
for(int y = 0; y < W; y++)
for(int j = i; j < l; j++)
update(i, l, x, y, D[i][j][x][y] + D[j + 1][l][x][y]);
}
else {
for(int x = 0; x < H; x++)
for(int y = 0; y < W; y++) {
int C = grid[x][y] - '0' - 1;
if(C == l) update(l, l, x, y, 0);
}
}
solve(i, l);
}
}
int res = -1;
for(int l = 0; l < H; l++)
for(int i = 0; i < W; i++) {
if(D[0][N - 1][l][i] < res || res == -1)
res = D[0][N - 1][l][i];
}
cout << res << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
63052 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
63140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
63052 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
63140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
63052 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
63140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
63052 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
63140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
