oj.uz

Submission #217979

# Submission time Handle Problem Language Result Execution time Memory
217979 2020-03-31T11:32:09 Z SamAnd Robots (APIO13_robots) C++17
0 / 100
 100 ms 163844 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 503, K = 11, INF = 1000000009;
const int xx[4] = {-1, 0, 1, 0};
const int yy[4] = {0, 1, 0, -1};
struct ban
{
    int x, y;
    ban(){}
    ban(int x, int y)
    {
        this->x = x;
        this->y = y;
    }
};

int n, m, k;
char a[N][N];
int sx[K], sy[K];

int c[N][N][4];
ban u[N][N][4];
void dfs(int x, int y, int z)
{
    c[x][y][z] = 1;
    int hx = x + xx[z];
    int hy = y + yy[z];
    int hz = z;
    if (!(hx >= 1 && hx <= n && hy >= 1 && hy <= m) || a[hx][hy] == 'x')
    {
        hx = x;
        hy = y;
    }
    else if (a[hx][hy] == 'C')
        hz = (z + 1) % 4;
    else if (a[hx][hy] == 'A')
        hz = (z - 1 + 4) % 4;
    if (hx == x && hy == y)
    {
        u[x][y][z] = ban(x, y);
        c[x][y][z] = 2;
        return;
    }
    if (!c[hx][hy][hz])
    {
        dfs(hx, hy, hz);
        u[x][y][z] = u[hx][hy][hz];
        c[x][y][z] = 2;
        return;
    }
    if (c[hx][hy][hz] == 2)
    {
        u[x][y][z] = u[hx][hy][hz];
        c[x][y][z] = 2;
        return;
    }
    u[x][y][z] = ban(-1, -1);
    c[x][y][z] = 2;
    return;
}

int dp[K][K][N][N];

bool cc[N][N];
deque<ban> q[N * N * K];

int main()
{
    freopen("input.txt", "r", stdin);
    scanf("%d%d%d", &k, &m, &n);
    for (int i = 1; i <= n; ++i)
        scanf(" %s", (a[i] + 1));
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if ('1' <= a[i][j] && a[i][j] <= '9')
            {
                sx[a[i][j] - '0'] = i;
                sy[a[i][j] - '0'] = j;
                a[i][j] = '.';
            }
        }
    }
    for (int i0 = 0; i0 < K; ++i0)
        for (int i1 = 0; i1 < K; ++i1)
            for (int i2 = 0; i2 < N; ++i2)
                for (int i3 = 0; i3 < N; ++i3)
                    dp[i0][i1][i2][i3] = INF;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            for (int k = 0; k < 4; ++k)
            {
                if (!c[i][j][k])
                {
                    dfs(i, j, k);
                }
            }
        }
    }
    for (int d = 1; d <= k; ++d)
    {
        for (int l = 1; l <= k - d + 1; ++l)
        {
            int r = l + d - 1;
            if (l == r)
                dp[l][r][sx[l]][sy[l]] = 0;
            for (int i = 1; i <= n; ++i)
            {
                for (int j = 1; j <= m; ++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]);
                }
            }
            memset(cc, false, sizeof cc);
            for (int i = 1; i <= n; ++i)
            {
                for (int j = 1; j <= m; ++j)
                {
                    if (dp[l][r][i][j] != INF)
                        q[dp[l][r][i][j]].push_back(ban(i, j));
                }
            }
            for (int ii = 0; ii < N * N * K; ++ii)
            {
                while (!q[ii].empty())
                {
                    ban t = q[ii].front();
                    q[ii].pop_front();
                    if (cc[t.x][t.y])
                        continue;
                    cc[t.x][t.y] = true;
                    for (int i = 0; i < 4; ++i)
                    {
                        ban h = u[t.x][t.y][i];
                        if (h.x == -1)
                            continue;
                        if (dp[l][r][t.x][t.y] + 1 < dp[l][r][h.x][h.y])
                        {
                            dp[l][r][h.x][h.y] = dp[l][r][t.x][t.y] + 1;
                            q[dp[l][r][h.x][h.y]].push_back(h);
                        }
                    }
                }
            }
        }
    }
    int ans = INF;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            ans = min(ans, dp[1][k][i][j]);
        }
    }
    if (ans == INF)
        printf("-1\n");
    else
        printf("%d\n", ans);
    return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:69:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("input.txt", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &k, &m, &n);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", (a[i] + 1));
         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 163844 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 163844 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 163844 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 163844 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -