oj.uz

Submission #218028

# Submission time Handle Problem Language Result Execution time Memory
218028 2020-03-31T12:47:56 Z SamAnd Robots (APIO13_robots) C++17
30 / 100
 348 ms 106608 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 503, 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 z[K][K];
int dp[(K * K) / 2][N][N];

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 i0 = 0; i0 < (K * K) / 2; ++i0)
        for (int i2 = 0; i2 < N; ++i2)
            for (int i3 = 0; i3 < N; ++i3)
                dp[i0][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);
                }
            }
        }
    }
    int zz = 0;
    for (int d = 1; d <= k; ++d)
    {
        for (int l = 0; l <= k - d; ++l)
        {
            int r = l + d - 1;
            z[l][r] = zz++;
        }
    }
    for (int d = 1; d <= k; ++d)
    {
        for (int l = 0; l <= k - d; ++l)
        {
            int r = l + d - 1;
            if (l == r)
                dp[z[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[z[l][r]][i][j] = min(dp[z[l][r]][i][j], dp[z[l][m]][i][j] + dp[z[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[z[l][r]][i][j] != INF)
                        q[dp[z[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].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[z[l][r]][t.x][t.y] + 1 < dp[z[l][r]][h.x][h.y])
                        {
                            dp[z[l][r]][h.x][h.y] = dp[z[l][r]][t.x][t.y] + 1;
                            q[dp[z[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[z[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:71: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:73: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 93688 KB Output is correct
2 Correct 71 ms 93688 KB Output is correct
3 Correct 75 ms 93816 KB Output is correct
4 Correct 71 ms 93688 KB Output is correct
5 Correct 71 ms 93776 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 93688 KB Output is correct
2 Correct 71 ms 93688 KB Output is correct
3 Correct 75 ms 93816 KB Output is correct
4 Correct 71 ms 93688 KB Output is correct
5 Correct 71 ms 93776 KB Output is correct
6 Correct 70 ms 93636 KB Output is correct
7 Correct 72 ms 93688 KB Output is correct
8 Correct 80 ms 93768 KB Output is correct
9 Correct 71 ms 93688 KB Output is correct
10 Correct 70 ms 93688 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 93688 KB Output is correct
2 Correct 71 ms 93688 KB Output is correct
3 Correct 75 ms 93816 KB Output is correct
4 Correct 71 ms 93688 KB Output is correct
5 Correct 71 ms 93776 KB Output is correct
6 Correct 70 ms 93636 KB Output is correct
7 Correct 72 ms 93688 KB Output is correct
8 Correct 80 ms 93768 KB Output is correct
9 Correct 71 ms 93688 KB Output is correct
10 Correct 70 ms 93688 KB Output is correct
11 Incorrect 348 ms 106608 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 93688 KB Output is correct
2 Correct 71 ms 93688 KB Output is correct
3 Correct 75 ms 93816 KB Output is correct
4 Correct 71 ms 93688 KB Output is correct
5 Correct 71 ms 93776 KB Output is correct
6 Correct 70 ms 93636 KB Output is correct
7 Correct 72 ms 93688 KB Output is correct
8 Correct 80 ms 93768 KB Output is correct
9 Correct 71 ms 93688 KB Output is correct
10 Correct 70 ms 93688 KB Output is correct
11 Incorrect 348 ms 106608 KB Output isn't correct
12 Halted 0 ms 0 KB -