Submission #1198879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198879		raphaelp	Robots (APIO13_robots)	C++20	60 / 100	1599 ms	109452 KiB

robots

#include <bits/stdc++.h>
using namespace std;
struct coord
{
    int x, y;
};
coord dfs(int dir, int x, int y, vector<vector<vector<coord>>> &Goto, vector<coord> &Tr, vector<string> &Grid)
{
    int dir2 = dir;
    if (Grid[x][y] == 'A')
        dir2 = (dir + 3) % 4;
    if (Grid[x][y] == 'C')
        dir2 = (dir + 1) % 4;
    if (Goto[dir][x][y].x != -1)
        return Goto[dir][x][y];
    Goto[dir][x][y] = {-2, -2};
    int x2 = x + Tr[dir2].x, y2 = y + Tr[dir2].y;
    if (x2 < 0 || y2 < 0 || x2 >= Grid.size() || y2 >= Grid[0].size())
        Goto[dir][x][y] = {x, y};
    else if (Grid[x2][y2] == 'x')
        Goto[dir][x][y] = {x, y};
    else
        Goto[dir][x][y] = dfs(dir2, x2, y2, Goto, Tr, Grid);
    return Goto[dir][x][y];
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N, W, H;
    cin >> N >> W >> H;
    vector<string> Grid(H);
    for (int i = 0; i < H; i++)
        cin >> Grid[i];
    vector<coord> Tr = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    vector<vector<vector<coord>>> Goto(4, vector<vector<coord>>(H, vector<coord>(W, {-1, -1})));
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            for (int dir = 0; dir < 4; dir++)
            {
                if (Goto[dir][i][j].x != -1)
                    continue;
                dfs(dir, i, j, Goto, Tr, Grid);
            }
        }
    }
    vector<vector<vector<vector<int>>>> dp(N, vector<vector<vector<int>>>(N, vector<vector<int>>(H, vector<int>(W, 100000000))));
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            int temp = Grid[i][j] - '1';
            if (temp >= 0 && temp <= 8)
                dp[temp][temp][i][j] = 0;
        }
    }
    int best = 100000000;
    for (int sz = 1; sz < N; sz++)
    {
        for (int l = 0; l < N - sz + 1; l++)
        {
            int r = l + sz - 1;
            priority_queue<vector<int>> PQ;
            for (int i = 0; i < H; i++)
                for (int j = 0; j < W; j++)
                    PQ.push({-dp[l][r][i][j], i, j});
            while (!PQ.empty())
            {
                int x = PQ.top()[1], y = PQ.top()[2], t = -PQ.top()[0];
                PQ.pop();
                if (dp[l][r][x][y] != t)
                    continue;
                for (int k = 0; k < 4; k++)
                {
                    if (Goto[k][x][y].x == -2)
                        continue;
                    if (dp[l][r][Goto[k][x][y].x][Goto[k][x][y].y] <= t + 1)
                        continue;
                    dp[l][r][Goto[k][x][y].x][Goto[k][x][y].y] = t + 1;
                    PQ.push({-t - 1, Goto[k][x][y].x, Goto[k][x][y].y});
                }
            }
        }
        for (int l = 0; l < N - sz; l++)
        {
            int r = l + sz;
            for (int i = 0; i < H; i++)
                for (int j = 0; j < W; j++)
                    for (int k = l; k < r; k++)
                        dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][k][i][j] + dp[k + 1][r][i][j]);
        }
    }
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            best = min(best, dp[0][N - 1][i][j]);
    if (best == 100000000)
        cout << -1;
    else
        cout << best;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40