oj.uz

Submission #915694

# Submission time Handle Problem Language Result Execution time Memory
915694 2024-01-24T14:47:26 Z Alcabel Robots (APIO13_robots) C++17
60 / 100
 1500 ms 100784 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];
char tmpvis[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];
            }
        }
    }
}

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);
            }
        }
    }
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
    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';
            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]);
                    }
                    tmpvis[i][j] = false;
                    dist[i][j] = dp[l][r][i][j];
                    // cerr << "i: " << i << ", j: " << j << ", dist: " << dist[i][j] << '\n';
                    q.emplace(dist[i][j], i, j);
                }
            }
            while (!q.empty()) {
                auto [d, i, j] = q.top();
                // cerr << "d: " << d << ", i: " << i << ", j: " << j << '\n;
                q.pop();
                if (tmpvis[i][j]) {
                    continue;
                }
                dp[l][r][i][j] = dist[i][j];
                tmpvis[i][j] = true;
                for (int dir = 0; dir < 4; ++dir) {
                    auto [newI, newJ] = dest[i][j][dir];
                    if (newI != -1 && dist[newI][newJ] > dist[i][j] + 1) {
                        dist[newI][newJ] = dist[i][j] + 1;
                        q.emplace(dist[newI][newJ], newI, newJ);
                    }
                }
            }
        }
    }
    /*cerr << dp[2][2][0][6] << '\n';
    cerr << dp[3][3][0][6] << '\n';
    cerr << dp[2][3][0][6] << '\n';
    cerr << dp[1][1][0][0] << '\n';
    cerr << dp[0][0][0][0] << '\n';
    cerr << dp[0][1][0][0] << '\n';*/
    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 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 425 ms 92368 KB Output is correct
12 Correct 6 ms 10840 KB Output is correct
13 Correct 235 ms 70100 KB Output is correct
14 Correct 666 ms 92364 KB Output is correct
15 Correct 414 ms 93392 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 425 ms 92368 KB Output is correct
12 Correct 6 ms 10840 KB Output is correct
13 Correct 235 ms 70100 KB Output is correct
14 Correct 666 ms 92364 KB Output is correct
15 Correct 414 ms 93392 KB Output is correct
16 Correct 1101 ms 100784 KB Output is correct
17 Execution timed out 1569 ms 100012 KB Time limit exceeded
18 Halted 0 ms 0 KB -