답안 #363669

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
363669 2021-02-06T19:03:37 Z dolphingarlic Connect (CEOI06_connect) C++14
100 / 100
70 ms 51052 KB
#include <bits/stdc++.h>
using namespace std;

struct State {
    State *prv;
    int cost, type;

    State(int _cost = 10000) : prv(nullptr), cost(_cost), type(-1) {}
    State(State *_prv, int _type) : prv(_prv), type(_type), cost(_prv->cost) {
        if (type < 4) cost++;
        else if (type < 10) cost += 2;
    }
};

State *construct(State *A, int typeA, State *B = nullptr, int typeB = -1) {
    if (!A && !B) return nullptr;
    if (!A) return new State(B, typeB);
    if (!B) return new State(A, typeA);
    if (A->cost < B->cost) return new State(A, typeA);
    if (A->cost > B->cost) return new State(B, typeB);
}

string grid[25];
State *dp[12][40][1 << 13];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int r, c;
    cin >> r >> c;
    getline(cin, grid[0]); // Buffer stuff >:(
    for (int i = 0; i < r; i++) getline(cin, grid[i]);
    int n = r >> 1, m = c >> 1;

    dp[n - 1][0][0] = new State(0);
    for (int j = 1; j <= m; j++) {
        for (int i = 0; i < n; i++) {
            for (int mask = 0; mask < (1 << n + 1); mask++) {
                int r = mask & (1 << i), d = mask & (1 << i + 1);
                // You can't connect over a blocked corridor
                if (r && grid[2 * i + 1][2 * j] == '|') continue;
                if (d && grid[2 * i + 2][2 * j - 1] == '-') continue;
                // An 'X' can't have more than 1 paths going out from it
                if (r && d && grid[2 * i + 1][2 * j - 1] == 'X') continue;
                // Casework for the DP
                if (!i) {
                    int prv_base = (mask >> 2) << 1;
                    if (grid[2 * i + 1][2 * j - 1] == 'X') {
                        if (r || d) {
                            if (r) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base], 1);
                            if (d) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base], 2);
                        } else dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base + 1], 3);
                    } else {
                        if (r && d) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base], 7);
                        else if (r || d) {
                            if (r) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base + 1], 8);
                            if (d) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base + 1], 9);
                        } else dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base], 10);
                    }
                } else {
                    int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
                    if (grid[2 * i + 1][2 * j - 1] == 'X') {
                        if (r || d) {
                            if (r) dp[i][j][mask] = construct(dp[i - 1][j][prv_base], 1);
                            if (d) dp[i][j][mask] = construct(dp[i - 1][j][prv_base], 2);
                        } else dp[i][j][mask] = construct(
                                dp[i - 1][j][prv_base + (1 << i)], 0,
                                dp[i - 1][j][prv_base + (1 << i + 1)], 3);
                    } else {
                        if (r && d) dp[i][j][mask] = construct(dp[i - 1][j][prv_base], 7);
                        else if (r || d) {
                            if (r) dp[i][j][mask] = construct(
                                    dp[i - 1][j][prv_base + (1 << i)], 4,
                                    dp[i - 1][j][prv_base + (1 << i + 1)], 8);
                            if (d) dp[i][j][mask] = construct(
                                    dp[i - 1][j][prv_base + (1 << i)], 5,
                                    dp[i - 1][j][prv_base + (1 << i + 1)], 9);
                        } else dp[i][j][mask] = construct(
                                dp[i - 1][j][prv_base + (1 << i) + (1 << i + 1)], 6,
                                dp[i - 1][j][prv_base], 10);
                    }
                }
            }
        }
    }
    cout << dp[n - 1][m][0]->cost << '\n';
    State *curr = dp[n - 1][m][0];
    for (int j = m - 1; ~j; j--) for (int i = n - 1; ~i; i--) {
        if (curr->type == 0) grid[2 * i][2 * j + 1] = '.';
        else if (curr->type == 1) grid[2 * i + 1][2 * j + 2] = '.';
        else if (curr->type == 2) grid[2 * i + 2][2 * j + 1] = '.';
        else if (curr->type == 3) grid[2 * i + 1][2 * j] = '.';
        else if (curr->type == 4) grid[2 * i][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j + 2] = '.';
        else if (curr->type == 5) grid[2 * i][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 2][2 * j + 1] = '.';
        else if (curr->type == 6) grid[2 * i][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j] = '.';
        else if (curr->type == 7) grid[2 * i + 1][2 * j + 2] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 2][2 * j + 1] = '.';
        else if (curr->type == 8) grid[2 * i + 1][2 * j + 2] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j] = '.';
        else if (curr->type == 9) grid[2 * i + 2][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j] = '.';
        curr = curr->prv;
    }
    for (int i = 0; i < r; i++) cout << grid[i] << '\n';
    return 0;
}

Compilation message

connect.cpp: In constructor 'State::State(State*, int)':
connect.cpp:6:15: warning: 'State::type' will be initialized after [-Wreorder]
    6 |     int cost, type;
      |               ^~~~
connect.cpp:6:9: warning:   'int State::cost' [-Wreorder]
    6 |     int cost, type;
      |         ^~~~
connect.cpp:9:5: warning:   when initialized here [-Wreorder]
    9 |     State(State *_prv, int _type) : prv(_prv), type(_type), cost(_prv->cost) {
      |     ^~~~~
connect.cpp: In function 'int main()':
connect.cpp:37:47: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   37 |             for (int mask = 0; mask < (1 << n + 1); mask++) {
      |                                             ~~^~~
connect.cpp:38:61: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   38 |                 int r = mask & (1 << i), d = mask & (1 << i + 1);
      |                                                           ~~^~~
connect.cpp:60:53: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   60 |                     int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
      |                                                   ~~^~~
connect.cpp:60:84: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   60 |                     int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
      |                                                                                  ~~^~~
connect.cpp:60:74: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   60 |                     int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
      |                                                                 ~~~~~~~~~^~~~~~~~~~~~~~
connect.cpp:67:65: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   67 |                                 dp[i - 1][j][prv_base + (1 << i + 1)], 3);
      |                                                               ~~^~~
connect.cpp:73:69: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   73 |                                     dp[i - 1][j][prv_base + (1 << i + 1)], 8);
      |                                                                   ~~^~~
connect.cpp:76:69: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   76 |                                     dp[i - 1][j][prv_base + (1 << i + 1)], 9);
      |                                                                   ~~^~~
connect.cpp:78:76: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   78 |                                 dp[i - 1][j][prv_base + (1 << i) + (1 << i + 1)], 6,
      |                                                                          ~~^~~
connect.cpp: In function 'State* construct(State*, int, State*, int)':
connect.cpp:21:1: warning: control reaches end of non-void function [-Wreturn-type]
   21 | }
      | ^
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 2 ms 1900 KB Output is correct
5 Correct 16 ms 12140 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 1 ms 1004 KB Output is correct
8 Correct 2 ms 1260 KB Output is correct
9 Correct 3 ms 2284 KB Output is correct
10 Correct 4 ms 3584 KB Output is correct
11 Correct 4 ms 3052 KB Output is correct
12 Correct 7 ms 5868 KB Output is correct
13 Correct 8 ms 6636 KB Output is correct
14 Correct 8 ms 7788 KB Output is correct
15 Correct 10 ms 9964 KB Output is correct
16 Correct 13 ms 13184 KB Output is correct
17 Correct 21 ms 15212 KB Output is correct
18 Correct 39 ms 28396 KB Output is correct
19 Correct 70 ms 51052 KB Output is correct
20 Correct 42 ms 33260 KB Output is correct