oj.uz

답안 #217985

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
217985 2020-03-31T11:36:18 Z SamAnd 로봇 (APIO13_robots) C++17
60 / 100
 261 ms 81272 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 303, 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];
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] - '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].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][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: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 51 ms 67576 KB Output is correct
2 Correct 50 ms 67576 KB Output is correct
3 Correct 49 ms 67576 KB Output is correct
4 Correct 50 ms 67704 KB Output is correct
5 Correct 50 ms 67704 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 67576 KB Output is correct
2 Correct 50 ms 67576 KB Output is correct
3 Correct 49 ms 67576 KB Output is correct
4 Correct 50 ms 67704 KB Output is correct
5 Correct 50 ms 67704 KB Output is correct
6 Correct 50 ms 67576 KB Output is correct
7 Correct 50 ms 67704 KB Output is correct
8 Correct 50 ms 67576 KB Output is correct
9 Correct 49 ms 67576 KB Output is correct
10 Correct 49 ms 67704 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 67576 KB Output is correct
2 Correct 50 ms 67576 KB Output is correct
3 Correct 49 ms 67576 KB Output is correct
4 Correct 50 ms 67704 KB Output is correct
5 Correct 50 ms 67704 KB Output is correct
6 Correct 50 ms 67576 KB Output is correct
7 Correct 50 ms 67704 KB Output is correct
8 Correct 50 ms 67576 KB Output is correct
9 Correct 49 ms 67576 KB Output is correct
10 Correct 49 ms 67704 KB Output is correct
11 Correct 191 ms 76024 KB Output is correct
12 Correct 54 ms 72568 KB Output is correct
13 Correct 121 ms 72056 KB Output is correct
14 Correct 261 ms 81272 KB Output is correct
15 Correct 174 ms 73208 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 67576 KB Output is correct
2 Correct 50 ms 67576 KB Output is correct
3 Correct 49 ms 67576 KB Output is correct
4 Correct 50 ms 67704 KB Output is correct
5 Correct 50 ms 67704 KB Output is correct
6 Correct 50 ms 67576 KB Output is correct
7 Correct 50 ms 67704 KB Output is correct
8 Correct 50 ms 67576 KB Output is correct
9 Correct 49 ms 67576 KB Output is correct
10 Correct 49 ms 67704 KB Output is correct
11 Correct 191 ms 76024 KB Output is correct
12 Correct 54 ms 72568 KB Output is correct
13 Correct 121 ms 72056 KB Output is correct
14 Correct 261 ms 81272 KB Output is correct
15 Correct 174 ms 73208 KB Output is correct
16 Execution timed out 17 ms 24320 KB Time limit exceeded (wall clock)
17 Halted 0 ms 0 KB -