Submission #478047

#	Time	Username	Problem	Language	Result	Execution time	Memory
478047		ThaiBaHung	Robots (APIO13_robots)	C++14	30 / 100	284 ms	144780 KiB

robots

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 503;
int m, n, k;
const int X[] = {0, 1, 0, -1};
const int Y[] = {1, 0, -1, 0};
typedef pair < int, int > ii;
ii nxt[N][N][4];
bool vs[N][N][4];
int dp[N][N][10][10];
char a[N][N];
typedef pair < ii, ii > iii;
vector < iii > val[N * N];

bool thoaman(int i, int j)
{
    if (i < 1 || j < 1 || i > m || j > n) return false;
    if (a[i][j] == 'x') return false;
    return true;
}

ii tim_pos(int i, int j, int dir)
{
    //cout << i << " " << j << " " << dir << '\n';
    if (vs[i][j][dir]) return nxt[i][j][dir];

    vs[i][j][dir] = true;
    int nxt_i = i + X[dir], nxt_j = j + Y[dir];
    if (!thoaman(nxt_i, nxt_j))
        nxt[i][j][dir] = {i, j};

    if (a[nxt_i][nxt_j] == '.')
        nxt[i][j][dir] = tim_pos(nxt_i, nxt_j, dir);

    if ('1' <= a[nxt_i][nxt_j] && a[nxt_i][nxt_j] <= '9')
        nxt[i][j][dir] = tim_pos(nxt_i, nxt_j, dir);

    if (a[nxt_i][nxt_j] == 'A')
        nxt[i][j][dir] = tim_pos(nxt_i, nxt_j, (dir + 3) % 4);

    if (a[nxt_i][nxt_j] == 'C')
        nxt[i][j][dir] = tim_pos(nxt_i, nxt_j, (dir + 1) % 4);

    return nxt[i][j][dir];
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("t.inp","r",stdin); freopen("t.out","w",stdout);

    cin >> k >> n >> m;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> a[i][j];
            for (int t = 0; t < 4; t++)
                nxt[i][j][t] = {-1, -1};
        }

    memset(vs, false, sizeof vs);
    memset(dp, 0x3f, sizeof dp);

    tim_pos(5, 5, 0);

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (a[i][j] != 'x')
            {
                for (int t = 0; t < 4; t++)
                    nxt[i][j][t] = tim_pos(i, j, t);

                int cs = 0;

                if ('1' <= a[i][j] && a[i][j] <= '9')
                dp[i][j][a[i][j] - '1' + 1][a[i][j] - '1' + 1] = 0,
                cs = a[i][j] - '1' + 1,
                val[0].push_back({{i, j}, {cs, cs}});
            }

    int res = 1e9 + 3;
    for (int gt = 0; gt <= m * n; gt++)
        for (iii cur : val[gt])
        {
            int i = cur.fi.fi, j = cur.fi.se;
            int lo = cur.se.fi, hi = cur.se.se;
            if (dp[i][j][lo][hi] != gt) continue;

            if (lo == 1 && hi == k)
            {
                res = min(res, gt);
                cout << res;
                return 0;
            }

            for (int u = lo - 1; u >= 1; u--)
                if (dp[i][j][u][lo - 1] < 1e9 && dp[i][j][u][hi] > dp[i][j][u][lo - 1] + dp[i][j][lo][hi])
                {
                    dp[i][j][u][hi] = dp[i][j][u][lo - 1] + dp[i][j][lo][hi];
                    val[dp[i][j][u][hi]].push_back({{i, j}, {u, hi}});
                    if (u == 1 && hi == k) res = min(res, dp[i][j][u][hi]);
                }

            for (int v = hi + 1; v <= k; v++)
                if (dp[i][j][hi + 1][v] < 1e9 && dp[i][j][lo][v] > dp[i][j][lo][hi] + dp[i][j][hi + 1][v])
                {
                    dp[i][j][lo][v] = dp[i][j][hi + 1][v] + dp[i][j][lo][hi];
                    val[dp[i][j][lo][v]].push_back({{i, j}, {lo, v}});
                    if (lo == 1 && v == k) res = min(res, dp[i][j][lo][v]);
                }

            for (int u = lo - 1; u >= 1; u--)
                for (int v = hi + 1; v <= k; v++)
                    if (dp[i][j][u][lo - 1] < 1e9 && dp[i][j][hi + 1][v] < 1e9)
                    {
                        if (dp[i][j][u][v] > dp[i][j][u][lo - 1] + gt + dp[i][j][hi + 1][v])
                        {
                            dp[i][j][u][v] = dp[i][j][u][lo - 1] + gt + dp[i][j][hi + 1][v];
                            val[dp[i][j][u][v]].push_back({{i, j}, {u, v}});
                            if (u == 1 && v == k) res = min(res, dp[i][j][u][v]);
                        }
                    }

            for (int t = 0; t < 4; t++)
            {
                int nxt_i = nxt[i][j][t].fi, nxt_j = nxt[i][j][t].se;

                if (nxt_i == -1) continue;

                if (dp[nxt_i][nxt_j][lo][hi] > gt + 1)
                {
                    dp[nxt_i][nxt_j][lo][hi] = gt + 1;
                    val[gt + 1].push_back({{nxt_i, nxt_j}, {lo, hi}});
                }
            }
        }

    if (res > 1e9) res = -1;
    cout << res;
}

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