oj.uz

답안 #915703

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915703 2024-01-24T15:06:02 Z Alcabel 로봇 (APIO13_robots) C++17
30 / 100
 123 ms 133456 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxc = 500, maxn = 10;
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) {
                    ++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) {
                            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 67932 KB Output is correct
2 Correct 19 ms 68104 KB Output is correct
3 Correct 19 ms 68188 KB Output is correct
4 Correct 21 ms 68108 KB Output is correct
5 Correct 19 ms 68188 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 67932 KB Output is correct
2 Correct 19 ms 68104 KB Output is correct
3 Correct 19 ms 68188 KB Output is correct
4 Correct 21 ms 68108 KB Output is correct
5 Correct 19 ms 68188 KB Output is correct
6 Correct 19 ms 67928 KB Output is correct
7 Correct 20 ms 67932 KB Output is correct
8 Correct 19 ms 68188 KB Output is correct
9 Correct 19 ms 67932 KB Output is correct
10 Correct 19 ms 68188 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 67932 KB Output is correct
2 Correct 19 ms 68104 KB Output is correct
3 Correct 19 ms 68188 KB Output is correct
4 Correct 21 ms 68108 KB Output is correct
5 Correct 19 ms 68188 KB Output is correct
6 Correct 19 ms 67928 KB Output is correct
7 Correct 20 ms 67932 KB Output is correct
8 Correct 19 ms 68188 KB Output is correct
9 Correct 19 ms 67932 KB Output is correct
10 Correct 19 ms 68188 KB Output is correct
11 Correct 82 ms 126548 KB Output is correct
12 Correct 24 ms 72284 KB Output is correct
13 Correct 46 ms 107088 KB Output is correct
14 Incorrect 123 ms 133456 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 67932 KB Output is correct
2 Correct 19 ms 68104 KB Output is correct
3 Correct 19 ms 68188 KB Output is correct
4 Correct 21 ms 68108 KB Output is correct
5 Correct 19 ms 68188 KB Output is correct
6 Correct 19 ms 67928 KB Output is correct
7 Correct 20 ms 67932 KB Output is correct
8 Correct 19 ms 68188 KB Output is correct
9 Correct 19 ms 67932 KB Output is correct
10 Correct 19 ms 68188 KB Output is correct
11 Correct 82 ms 126548 KB Output is correct
12 Correct 24 ms 72284 KB Output is correct
13 Correct 46 ms 107088 KB Output is correct
14 Incorrect 123 ms 133456 KB Output isn't correct
15 Halted 0 ms 0 KB -