oj.uz

답안 #218022

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
218022 2020-03-31T12:32:11 Z SamAnd 로봇 (APIO13_robots) C++17
30 / 100
 108 ms 86136 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 302, K = 9, INF = 1000000009;
const int xx[4] = {-1, 0, 1, 0};
const int yy[4] = {0, 1, 0, -1};
struct ban
{
    short 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));
         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 39168 KB Output is correct
2 Correct 38 ms 39168 KB Output is correct
3 Correct 38 ms 39168 KB Output is correct
4 Correct 38 ms 39296 KB Output is correct
5 Correct 38 ms 39296 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 39168 KB Output is correct
2 Correct 38 ms 39168 KB Output is correct
3 Correct 38 ms 39168 KB Output is correct
4 Correct 38 ms 39296 KB Output is correct
5 Correct 38 ms 39296 KB Output is correct
6 Correct 39 ms 39296 KB Output is correct
7 Correct 39 ms 39168 KB Output is correct
8 Correct 38 ms 39288 KB Output is correct
9 Correct 39 ms 39292 KB Output is correct
10 Correct 39 ms 39296 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 39168 KB Output is correct
2 Correct 38 ms 39168 KB Output is correct
3 Correct 38 ms 39168 KB Output is correct
4 Correct 38 ms 39296 KB Output is correct
5 Correct 38 ms 39296 KB Output is correct
6 Correct 39 ms 39296 KB Output is correct
7 Correct 39 ms 39168 KB Output is correct
8 Correct 38 ms 39288 KB Output is correct
9 Correct 39 ms 39292 KB Output is correct
10 Correct 39 ms 39296 KB Output is correct
11 Runtime error 108 ms 86136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 39168 KB Output is correct
2 Correct 38 ms 39168 KB Output is correct
3 Correct 38 ms 39168 KB Output is correct
4 Correct 38 ms 39296 KB Output is correct
5 Correct 38 ms 39296 KB Output is correct
6 Correct 39 ms 39296 KB Output is correct
7 Correct 39 ms 39168 KB Output is correct
8 Correct 38 ms 39288 KB Output is correct
9 Correct 39 ms 39292 KB Output is correct
10 Correct 39 ms 39296 KB Output is correct
11 Runtime error 108 ms 86136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -