Algoogle

Algorithm for Programming Contest

AOJ 2169 Colored Octahedra

Category: AOJ Tag: implementation

Colored Octahedra

問題概要


8枚の正三角形の色が渡されるので, 何通りの正八面体が作れるか.
ただし回転しておなじになるものは重複して数えない.

解法


8枚なのでとりあえず順列を全て試す.
まだ未チェックだったら答えに追加し, その順列と回転してできる順列をチェック済みにする.
回転は右に回すのと手前に回すのを新しい順列が作られる限り繰り返せばよい.

コード


(2169.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) begin(u),end(u)
#define pb push_back
map<string,int> cnt;
set<int> done;
const int rot[][8] = {{1,2,3,0,5,6,7,4},
                      {6,7,1,0,2,3,5,4}};

void dfs(string &cl){
    int a = atoi(cl.c_str());
    if(done.count(a)) return;
    done.insert(a);
    rep(i,2){
        string tcl;
        rep(j,8) tcl.pb(cl[rot[i][j]]);
        dfs(tcl);
    }
    return;
}

int solve(){
    string cl;
    int idx = 0, ans = 0;
    for(auto it = begin(cnt); it != end(cnt); it++, idx++)
        rep(j,it->second) cl.pb(idx+'1');
    sort(all(cl));
    do{
        int a = atoi(cl.c_str());
        if(done.count(a)) continue;
        ans++;
        dfs(cl);
    } while(next_permutation(all(cl)));
    return ans;
}

bool input(){
    string s;
    if(!(cin >> s)) return 0;
    cnt.clear(); done.clear();
    cnt[s]++;
    rep(i,7) { cin >> s; cnt[s]++;}
    return 1;
}
signed main(){
    while(input()) cout << solve() << endl;
    return 0;
}

Comments