Submission #218015

# Submission time Handle Problem Language Result Execution time Memory
218015 2020-03-31T12:25:39 Z SamAnd Robots (APIO13_robots) C++17
30 / 100
274 ms 163840 KB
#include <bits/stdc++.h>
using namespace std;
const int N = 502, K = 9, 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;

bool cc[N][N];
vector<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] - '1'] = i;
                sy[a[i][j] - '1'] = j;
                a[i][j] = '.';
            }
        }
    }
    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);
                }
            }
        }
    }
    //printf("PRRRRR\n");
    dp = new int***[K];
    for (int i = 0; i < K; ++i)
    {
        dp[i] = new int**[K - i];
        for (int j = 0; j <= K - i; ++j)
        {
            dp[i][j] = new int*[N];
            for (int x = 0; x < N; ++x)
            {
                dp[i][j][x] = new int[N];
                for (int y = 0; y < N; ++y)
                    dp[i][j][x][y] = INF;
            }
        }
    }
    for (int d = 0; d < k; ++d)
    {
        for (int l = 0; l <= k - d; ++l)
        {
            if (d == 0)
                dp[l][d][sx[l]][sy[l]] = 0;
            for (int i = 1; i <= n; ++i)
            {
                for (int j = 1; j <= m; ++j)
                {
                    for (int m = 0; m < d; ++m)
                        dp[l][d][i][j] = min(dp[l][d][i][j], dp[l][m][i][j] + dp[l + m + 1][d - m - 1][i][j]);
                }
            }
            memset(cc, false, sizeof cc);
            for (int i = 1; i <= n; ++i)
            {
                for (int j = 1; j <= m; ++j)
                {
                    if (dp[l][d][i][j] != INF)
                        q[dp[l][d][i][j]].push_back(ban(i, j));
                }
            }
            for (int ii = 0; ii < N * N * K; ++ii)
            {
                while (!q[ii].empty())
                {
                    ban t = q[ii].back();
                    q[ii].pop_back();
                    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][d][t.x][t.y] + 1 < dp[l][d][h.x][h.y])
                        {
                            dp[l][d][h.x][h.y] = dp[l][d][t.x][t.y] + 1;
                            q[dp[l][d][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[0][k - 1][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: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));
         ~~~~~^~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 94 ms 107512 KB Output is correct
2 Correct 93 ms 107512 KB Output is correct
3 Correct 92 ms 107512 KB Output is correct
4 Correct 93 ms 107640 KB Output is correct
5 Correct 93 ms 107640 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 94 ms 107512 KB Output is correct
2 Correct 93 ms 107512 KB Output is correct
3 Correct 92 ms 107512 KB Output is correct
4 Correct 93 ms 107640 KB Output is correct
5 Correct 93 ms 107640 KB Output is correct
6 Correct 96 ms 107512 KB Output is correct
7 Correct 94 ms 107576 KB Output is correct
8 Correct 96 ms 107512 KB Output is correct
9 Correct 95 ms 107512 KB Output is correct
10 Correct 99 ms 107640 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 94 ms 107512 KB Output is correct
2 Correct 93 ms 107512 KB Output is correct
3 Correct 92 ms 107512 KB Output is correct
4 Correct 93 ms 107640 KB Output is correct
5 Correct 93 ms 107640 KB Output is correct
6 Correct 96 ms 107512 KB Output is correct
7 Correct 94 ms 107576 KB Output is correct
8 Correct 96 ms 107512 KB Output is correct
9 Correct 95 ms 107512 KB Output is correct
10 Correct 99 ms 107640 KB Output is correct
11 Runtime error 274 ms 163840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 94 ms 107512 KB Output is correct
2 Correct 93 ms 107512 KB Output is correct
3 Correct 92 ms 107512 KB Output is correct
4 Correct 93 ms 107640 KB Output is correct
5 Correct 93 ms 107640 KB Output is correct
6 Correct 96 ms 107512 KB Output is correct
7 Correct 94 ms 107576 KB Output is correct
8 Correct 96 ms 107512 KB Output is correct
9 Correct 95 ms 107512 KB Output is correct
10 Correct 99 ms 107640 KB Output is correct
11 Runtime error 274 ms 163840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -