백준2598 기둥만들기

작성일 | In

문제 링크

  • http://icpc.me/2598

문제 출처

  • 2004 KOI 초등부 3번

풀이

브루트포스를 열심히 하는 문제입니다.
(1) 기둥의 상태를 잘 표현하는 것, (2) 회전했을 때 동일한 기둥인지 판별하는 것, (3) 정육면체의 상태를 잘 표현하는 것, 3가지를 어떻게 효율적으로 구현할지 고민해보는 것이 좋습니다.

색이 4가지 종류 밖에 없기 때문에 각 색깔은 2비트로 표현할 수 있습니다. 옆면에 등장하는 16개의 면과 윗면까지 총 17개의 면을 표현해야 하므로 34비트가 필요합니다. 64bit 정수형으로 저장할 수 있습니다.

회전했을 때 동일한 기둥인지 판별하는 것은, 옆면들의 minimum cyclic shift를 저장하면 됩니다. 다시 말해, 4개의 옆면을 회전시켰을 때 사전순으로 가장 앞서는 것만 저장하면 됩니다. (ex. 2031 / 0312 / 3120 / 1203 중 0312만 저장)

정육면체의 상태를 나타내는 것은 위/앞/오른쪽, 총 3개의 면을 고정하면 됩니다.

위 3가지를 잘 조합하면 문제를 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

using ll = long long;

const array<int,4> SIDE[6] = { {5,1,4,3}, {5,2,4,0}, {5,3,4,1}, {0,4,2,5}, {0,1,2,3}, {0,3,2,1} };

string A[4];
map<array<int,3>, array<int,4>> mp;
array<int,4> fst[6];

int C_MAP[256];
inline int ID(char c){ return C_MAP[c]; }

void Init(){
    C_MAP['R'] = 0; C_MAP['G'] = 1; C_MAP['B'] = 2; C_MAP['Y'] = 3;
    for(int i=0; i<6; i++){
        array<int,3> a; array<int,4> b = SIDE[i];
        a[0] = i;
        for(int j=0; j<4; j++){
            a[1] = b[0]; a[2] = b[1];
            mp[a] = b; if(!j) fst[i] = b;
            rotate(b.begin(), b.begin()+1, b.end());
        }
    }
}

ll Norm(ll bit){
    vector<ll> vec, mn;
    vec.push_back(bit & 3); bit >>= 2;
    vec.push_back(bit & 255); bit >>= 8;
    vec.push_back(bit & 255); bit >>= 8;
    vec.push_back(bit & 255); bit >>= 8;
    vec.push_back(bit & 255); bit >>= 8;
    reverse(all(vec)); mn = vec;
    for(int i=0; i<4; i++){
        rotate(vec.begin(), vec.begin()+1, vec.begin()+4);
        mn = min(mn, vec);
    }
    for(int i=0; i<4; i++) bit = bit << 8 | mn[i];
    bit = bit << 2 | mn.back();
    return bit;
}

ll Check(const array<int,4> &a, const array<int,4> &b, const array<int,4> &c, const array<int,4> &d, int top){
    ll ret = 0;
    for(int i=0; i<4; i++){
        int bit = 0;
        array<int,4> now = {ID(A[0][a[i]]), ID(A[1][b[i]]), ID(A[2][c[i]]), ID(A[3][d[i]])};
        for(auto j : now) bit |= 1 << j, ret |= j, ret <<= 2;
        if(bit != 15) return 0;
    }
    ret |= top;
    return Norm(ret);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    Init();
    for(int i=0; i<4; i++) cin >> A[i];

    vector<ll> res;
    for(const auto &a : fst) for(const auto &b : mp) for(const auto &c : mp) for(const auto &d : mp)
        res.push_back(Check(a, b.y, c.y, d.y, ID(A[3][d.x[0]])));

    sort(all(res), greater<>());
    while(res.size() && !res.back()) res.pop_back();
    compress(res);
    cout << res.size();
}