Submission #940464

#	Time	Username	Problem	Language	Result	Execution time	Memory
940464		Ice_man	Robots (APIO13_robots)	C++14	100 / 100	1135 ms	102576 KiB

robots

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>

#define max 500
#define maxn 505
#define sm 9
#define maxlog 20
#define INF 1000000010
#define mod 998244353
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;

char c[maxn][maxn];
int dp[maxn][maxn][sm][sm];
int state[maxn][maxn][4];
pair<int, int> stops[maxn][maxn][4];

int n, h, w;

void read()
{

    cin >> n >> w >> h;

    h += 2;
    w += 2;

    for (int i = 0; i < w; ++i)
        c[0][i] = c[h - 1][i] = 'x';

    for (int i = 0; i < h; ++i)
        c[i][0] = c[i][w - 1] = 'x';

    for (int i = 1; i < h - 1; ++i)
        for (int j = 1; j < w - 1; ++j)
            cin >> c[i][j];

    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            for (int k = 0; k < n; ++k)
                for (int l = 0; l < n; ++l)
                    dp[i][j][k][l] = INF;
}

int dirx[] = {0, 1, 0, -1};
int diry[] = {1, 0, -1, 0};


pair<int, int> dfs(int i, int j, int k)
{
    if (state[i][j][k] == 2)
        return stops[i][j][k];

    if (state[i][j][k] == 1)
        return stops[i][j][k] = {i, j};

    state[i][j][k] = 1;
    int nk = k;
    if (c[i][j] == 'A')
        nk = (k + 3) % 4;

    if (c[i][j] == 'C')
        nk = (k + 1) % 4;

    int ni = i + dirx[nk], nj = j + diry[nk];

    if (c[ni][nj] == 'x')
    {
        state[i][j][k] = 2;
        return stops[i][j][k] = {i, j};
    }
    else
    {
        stops[i][j][k] = dfs(ni, nj, nk);
        if (state[ni][nj][nk] == 1)
            stops[i][j][k] = {i, j};
        else
            state[i][j][k] = 2;
        return stops[i][j][k];
    }
}


void solve()
{
    for (int len = 0; len < n; ++len)
    {
        for (int l = 0; l + len < n; ++l)
        {
            const int r = l + len;

            vector<vector<pair<int, int>>> v(maxn * maxn + 5);

            if (len == 0)
            {
                for (int i = 0; i < h; ++i)
                    for (int j = 0; j < w; ++j)
                        if (c[i][j] - '1' == l)
                        {
                            dp[i][j][l][r] = 0;
                            v[0].push_back({i, j});
                        }
            }
            else
            {
                for (int i = 0; i < h; ++i)
                    for (int j = 0; j < w; ++j)
                    {
                        int minn = INF;
                        for (int k = l; k < r; ++k)
                            minn = min(minn, dp[i][j][l][k] + dp[i][j][k + 1][r]);

                        dp[i][j][l][r] = minn;
                        if (minn < maxn * maxn)
                            v[minn].push_back({i, j});
                    }
            }

            for (int d = 0; d < maxn * maxn; ++d)
                for (pair <int, int> e : v[d])
                    for (int k = 0; k < 4; ++k)
                    {
                        pair <int, int> nb = dfs(e.X, e.Y, k);
                        if (dp[nb.X][nb.Y][l][r] > d + 1)
                        {
                            dp[nb.X][nb.Y][l][r] = d + 1;
                            v[d + 1].push_back({nb.X, nb.Y});
                        }
                    }
        }
    }
}


void print()
{
    int ans = INF;

    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            ans = min(ans, dp[i][j][0][n - 1]);

    if(ans == INF)
        cout << -1 << endl;
    else
        cout << ans << endl;
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);


    read();
    solve();
    print();



    return 0;
}

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