oj.uz

Submission #915711

# Submission time Handle Problem Language Result Execution time Memory
915711 2024-01-24T15:22:45 Z Alcabel Robots (APIO13_robots) C++17
100 / 100
 673 ms 145120 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxc = 500, maxn = 9;
const int deltaX[4] = {0, -1, 0, 1}, deltaY[4] = {1, 0, -1, 0};
char t[maxc][maxc];
pair<int, int> dest[maxc][maxc][4];
char vis[maxc][maxc][4];
int w, h;

pair<int, int> getDest(int x, int y, int dir) {
    if (vis[x][y][dir] == 1) {
        dest[x][y][dir] = {-1, -1};
        return {-1, -1};
    }
    if (vis[x][y][dir] == 2) {
        return dest[x][y][dir];
    }
    vis[x][y][dir] = 1;
    int newDir = dir;
    if (t[x][y] == 'A') {
        newDir = (dir < 3 ? dir + 1 : 0);
    } else if (t[x][y] == 'C') {
        newDir = (dir > 0 ? dir - 1 : 3);
    }
    int newX = x + deltaX[newDir], newY = y + deltaY[newDir];
    if (newX < 0 || newX >= h || newY < 0 || newY >= w || t[newX][newY] == 'x') {
        dest[x][y][dir] = {x, y};
    } else {
        dest[x][y][dir] = getDest(newX, newY, newDir);
    }
    vis[x][y][dir] = 2;
    return dest[x][y][dir];
}

const int inf = 1e9;
int dist[maxc][maxc];
int dp[maxn][maxn][maxc][maxc];

void bfs(int sx, int sy) {
    static queue<pair<int, int>> q;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            dist[i][j] = -1;
        }
    }
    dist[sx][sy] = 0;
    q.emplace(sx, sy);
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int dir = 0; dir < 4; ++dir) {
            auto [newX, newY] = dest[x][y][dir];
            if (newX != -1 && dist[newX][newY] == -1) {
                dist[newX][newY] = dist[x][y] + 1;
                q.emplace(newX, newY);
            }
        }
    }
    int num = t[sx][sy] - '1';
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (dist[i][j] != -1) {
                dp[num][num][i][j] = dist[i][j];
            }
        }
    }
}

const int maxd = maxn * maxc * maxc + 10;
vector<pair<int, int>> byDist[maxd];
// int distT[maxd], tt;

void solve() {
    int n;
    cin >> n >> w >> h;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> t[i][j];
        }
    }
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            // cerr << "i: " << i << ", j: " << j << '\n';
            for (int dir = 0; dir < 4; ++dir) {
                if (t[i][j] == 'x') {
                    dest[i][j][dir] = {-1, -1};
                    vis[i][j][dir] = 2;
                } else {
                    dest[i][j][dir] = getDest(i, j, dir);
                }
                // cerr << "dir: " << dir << ", dest: " << dest[i][j][dir].first << ' ' << dest[i][j][dir].second << '\n';
            }
        }
    }
    for (int l = 0; l < n; ++l) {
        for (int r = 0; r < n; ++r) {
            for (int i = 0; i < h; ++i) {
                for (int j = 0; j < w; ++j) {
                    dp[l][r][i][j] = inf;
                }
            }
        }
    }
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (t[i][j] >= '1' && t[i][j] <= '9') {
                bfs(i, j);
            }
        }
    }
    // tt = 0;
    for (int len = 2; len <= n; ++len) {
        for (int l = 0; l + len <= n; ++l) {
            int r = l + len - 1;
            // cerr << "l: " << l << ", r: " << r << '\n';
            // ++tt;
            for (int i = 0; i < h; ++i) {
                for (int j = 0; j < w; ++j) {
                    for (int m = l; m < r; ++m) {
                        dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][m][i][j] + dp[m + 1][r][i][j]);
                    }
                    dist[i][j] = dp[l][r][i][j];
                    if (dist[i][j] != inf) {
                        byDist[dist[i][j]].emplace_back(i, j);
                    }
                    // cerr << "i: " << i << ", j: " << j << ", dist: " << dist[i][j] << '\n';
                }
            }
            for (int start = 0; start < maxd; ++start) {
                while (!byDist[start].empty()) {
                    auto [i, j] = byDist[start].back();
                    byDist[start].pop_back();
                    dp[l][r][i][j] = dist[i][j];
                    for (int dir = 0; dir < 4; ++dir) {
                        auto [newI, newJ] = dest[i][j][dir];
                        if (newI != -1 && dist[newI][newJ] > dist[i][j] + 1) {
                            int newd = dist[i][j] + 1;
                            dist[newI][newJ] = newd;
                            byDist[newd].emplace_back(newI, newJ);
                        }
                    }
                }
                byDist[start].shrink_to_fit();
            }
        }
    }
    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]);
        }
    }
    if (ans == inf) {
        ans = -1;
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64092 KB Output is correct
2 Correct 24 ms 64088 KB Output is correct
3 Correct 23 ms 64228 KB Output is correct
4 Correct 25 ms 64172 KB Output is correct
5 Correct 25 ms 64092 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64092 KB Output is correct
2 Correct 24 ms 64088 KB Output is correct
3 Correct 23 ms 64228 KB Output is correct
4 Correct 25 ms 64172 KB Output is correct
5 Correct 25 ms 64092 KB Output is correct
6 Correct 24 ms 64088 KB Output is correct
7 Correct 26 ms 64600 KB Output is correct
8 Correct 25 ms 64092 KB Output is correct
9 Correct 26 ms 64092 KB Output is correct
10 Correct 28 ms 64252 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64092 KB Output is correct
2 Correct 24 ms 64088 KB Output is correct
3 Correct 23 ms 64228 KB Output is correct
4 Correct 25 ms 64172 KB Output is correct
5 Correct 25 ms 64092 KB Output is correct
6 Correct 24 ms 64088 KB Output is correct
7 Correct 26 ms 64600 KB Output is correct
8 Correct 25 ms 64092 KB Output is correct
9 Correct 26 ms 64092 KB Output is correct
10 Correct 28 ms 64252 KB Output is correct
11 Correct 350 ms 121368 KB Output is correct
12 Correct 23 ms 62548 KB Output is correct
13 Correct 198 ms 106068 KB Output is correct
14 Correct 457 ms 121340 KB Output is correct
15 Correct 334 ms 119412 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64092 KB Output is correct
2 Correct 24 ms 64088 KB Output is correct
3 Correct 23 ms 64228 KB Output is correct
4 Correct 25 ms 64172 KB Output is correct
5 Correct 25 ms 64092 KB Output is correct
6 Correct 24 ms 64088 KB Output is correct
7 Correct 26 ms 64600 KB Output is correct
8 Correct 25 ms 64092 KB Output is correct
9 Correct 26 ms 64092 KB Output is correct
10 Correct 28 ms 64252 KB Output is correct
11 Correct 350 ms 121368 KB Output is correct
12 Correct 23 ms 62548 KB Output is correct
13 Correct 198 ms 106068 KB Output is correct
14 Correct 457 ms 121340 KB Output is correct
15 Correct 334 ms 119412 KB Output is correct
16 Correct 373 ms 142672 KB Output is correct
17 Correct 673 ms 145120 KB Output is correct
18 Correct 390 ms 144256 KB Output is correct
19 Correct 395 ms 142672 KB Output is correct
20 Correct 531 ms 144936 KB Output is correct