Submission #915708

#	Time	Username	Problem	Language	Result	Execution time	Memory
915708		Alcabel	Robots (APIO13_robots)	C++17	60 / 100	199 ms	163840 KiB

robots

#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';
            int needcnt = 0, start = inf;
            ++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) {
                        ++needcnt;
                        if (distT[dist[i][j]] < tt) {
                            distT[dist[i][j]] = tt;
                            byDist[dist[i][j]].clear();
                        }
                        byDist[dist[i][j]].emplace_back(i, j);
                        start = min(start, dist[i][j]);
                    }
                    // cerr << "i: " << i << ", j: " << j << ", dist: " << dist[i][j] << '\n';
                }
            }
            while (needcnt > 0) {
                while (start < maxd && distT[start] < tt) {
                    distT[start] = tt;
                    byDist[start].clear();
                    ++start;
                }
                assert(start < maxd);
                while (!byDist[start].empty()) {
                    auto [i, j] = byDist[start].back();
                    byDist[start].pop_back();
                    dp[l][r][i][j] = dist[i][j];
                    --needcnt;
                    for (int dir = 0; dir < 4; ++dir) {
                        auto [newI, newJ] = dest[i][j][dir];
                        if (newI != -1 && dist[newI][newJ] > dist[i][j] + 1) {
                            ++needcnt;
                            int newd = dist[i][j] + 1;
                            dist[newI][newJ] = newd;
                            if (distT[newd] < tt) {
                                distT[newd] = tt;
                                byDist[newd].clear();
                            }
                            byDist[newd].emplace_back(newI, newJ);
                        }
                    }
                }
                ++start;
            }
        }
    }
    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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40