#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int inf = 1e9 + 20;
const int maxN = 5e2 + 20;
const int maxK = 10;
char grid[maxN][maxN];
int dp[maxK][maxK][maxN][maxN];
pair<int, int> nxt[maxN][maxN][4];
int N, M, K;
pair<int, int> calc(int cx, int cy, int d) {
if (nxt[cx][cy][d].first == -2) {
return (nxt[cx][cy][d] = make_pair(-1, -1));
}
if (nxt[cx][cy][d].first) {
return nxt[cx][cy][d];
}
int nd = d;
if (grid[cx][cy] == 'C') {
nd = (nd + 1) % 4;
}
if (grid[cx][cy] == 'A') {
nd = (nd + 3) % 4;
}
int nx = cx + dx[nd];
int ny = cy + dy[nd];
if (1 <= nx && nx <= N && 1 <= ny && ny <= M && grid[nx][ny] != 'x') {
nxt[cx][cy][d] = make_pair(-2, -2);
return (nxt[cx][cy][d] = calc(nx, ny, nd));
}
else {
return (nxt[cx][cy][d] = make_pair(cx, cy));
}
}
void dijkstra(int lt, int rt) {
vector<pair<int, pair<int, int>>> S;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (dp[lt][rt][i][j] != inf) {
S.emplace_back(dp[lt][rt][i][j], make_pair(i, j));
}
}
}
sort(S.begin(), S.end());
deque<pair<int, int>> Q;
Q.emplace_back(S[0].second);
int pt = 1;
while (!Q.empty()) {
int cx = Q.front().first;
int cy = Q.front().second;
int cd = dp[lt][rt][cx][cy];
while (pt < (int)S.size() && S[pt].first <= cd) {
int nx = S[pt].second.first;
int ny = S[pt].second.second;
if (dp[lt][rt][nx][ny] == S[pt].first) {
Q.emplace_front(nx, ny);
}
pt++;
}
cx = Q.front().first;
cy = Q.front().second;
cd = dp[lt][rt][cx][cy];
Q.pop_front();
if (dp[lt][rt][cx][cy] != cd) {
continue;
}
for (int d = 0; d < 4; d++) {
int nx = nxt[cx][cy][d].first;
int ny = nxt[cx][cy][d].second;
if (nx != -1 && dp[lt][rt][nx][ny] > cd + 1) {
dp[lt][rt][nx][ny] = cd + 1;
Q.emplace_back(nx, ny);
}
}
}
}
void just_do_it() {
fill_n(&dp[0][0][0][0], maxK * maxK * maxN * maxN, inf);
cin >> K >> M >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> grid[i][j];
if ('1' <= grid[i][j] && grid[i][j] <= '9') {
int d = grid[i][j] - '0';
dp[d][d][i][j] = 0;
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
for (int d = 0; d < 4; d++) {
if (grid[i][j] == 'x') {
nxt[i][j][d] = make_pair(-1, -1);
}
else {
calc(i, j, d);
}
}
}
}
for (int i = 1; i <= K; i++) {
dijkstra(i, i);
}
for (int len = 2; len <= K; len++) {
for (int i = 1, j = len; j <= K; i++, j++) {
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= M; y++) {
for (int k = i; k < j; k++) {
dp[i][j][x][y] = min(dp[i][j][x][y], dp[i][k][x][y] + dp[k + 1][j][x][y]);
}
}
}
dijkstra(i, j);
}
}
int res = inf;
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= M; y++) {
res = min(res, dp[1][K][x][y]);
}
}
if (res == inf) {
cout << -1;
}
else {
cout << res;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
106060 KB |
Output is correct |
| 2 |
Runtime error |
148 ms |
163840 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
106060 KB |
Output is correct |
| 2 |
Runtime error |
148 ms |
163840 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
106060 KB |
Output is correct |
| 2 |
Runtime error |
148 ms |
163840 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
106060 KB |
Output is correct |
| 2 |
Runtime error |
148 ms |
163840 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
