oj.uz

답안 #915708

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915708 2024-01-24T15:18:44 Z Alcabel 로봇 (APIO13_robots) C++17
60 / 100
 199 ms 163840 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';
            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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 61788 KB Output is correct
2 Correct 17 ms 61788 KB Output is correct
3 Correct 18 ms 61788 KB Output is correct
4 Correct 17 ms 61788 KB Output is correct
5 Correct 19 ms 61788 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 61788 KB Output is correct
2 Correct 17 ms 61788 KB Output is correct
3 Correct 18 ms 61788 KB Output is correct
4 Correct 17 ms 61788 KB Output is correct
5 Correct 19 ms 61788 KB Output is correct
6 Correct 18 ms 61788 KB Output is correct
7 Correct 17 ms 61788 KB Output is correct
8 Correct 17 ms 61784 KB Output is correct
9 Correct 17 ms 61788 KB Output is correct
10 Correct 18 ms 61784 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 61788 KB Output is correct
2 Correct 17 ms 61788 KB Output is correct
3 Correct 18 ms 61788 KB Output is correct
4 Correct 17 ms 61788 KB Output is correct
5 Correct 19 ms 61788 KB Output is correct
6 Correct 18 ms 61788 KB Output is correct
7 Correct 17 ms 61788 KB Output is correct
8 Correct 17 ms 61784 KB Output is correct
9 Correct 17 ms 61788 KB Output is correct
10 Correct 18 ms 61784 KB Output is correct
11 Correct 97 ms 130012 KB Output is correct
12 Correct 22 ms 64092 KB Output is correct
13 Correct 42 ms 109916 KB Output is correct
14 Correct 135 ms 134356 KB Output is correct
15 Correct 76 ms 125804 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 61788 KB Output is correct
2 Correct 17 ms 61788 KB Output is correct
3 Correct 18 ms 61788 KB Output is correct
4 Correct 17 ms 61788 KB Output is correct
5 Correct 19 ms 61788 KB Output is correct
6 Correct 18 ms 61788 KB Output is correct
7 Correct 17 ms 61788 KB Output is correct
8 Correct 17 ms 61784 KB Output is correct
9 Correct 17 ms 61788 KB Output is correct
10 Correct 18 ms 61784 KB Output is correct
11 Correct 97 ms 130012 KB Output is correct
12 Correct 22 ms 64092 KB Output is correct
13 Correct 42 ms 109916 KB Output is correct
14 Correct 135 ms 134356 KB Output is correct
15 Correct 76 ms 125804 KB Output is correct
16 Correct 128 ms 142932 KB Output is correct
17 Runtime error 199 ms 163840 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -