Algoogle

Algorithm for Programming Contest

AOJ 1253 Dice Puzzle

Category: AOJ Tag: implementation

Dice Puzzle

問題概要


3*3*3の立方体の各位置に隣り合う面の和が7になるようにサイコロを置く.
このとき立方体の上から見える数字と前から見える数字が与えられる. ただし0の場合はなんでもよい
右から見える数字の総和としてありえるものを求めよ.

解法


全ての位置に対して全ての向きのサイコロを置いてみる.
枝刈りで大量に刈れるので問題なく全探索できる.

コード


(1253.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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) begin(u),end(u)
#define pb push_back
struct dice{
    int val[6];
    void roti(){int t=val[5];val[5]=val[1];val[1]=val[4];val[4]=val[0];val[0]=t;}
    void rotj(){int t=val[3];val[3]=val[1];val[1]=val[2];val[2]=val[0];val[0]=t;}
    void rotk(){int t=val[3];val[3]=val[4];val[4]=val[2];val[2]=val[5];val[5]=t;}
};
int F[3][3], T[3][3];
dice cube[3][3][3];
vector<int> ans;

void rec(int cur){
    if(cur == 27){
        int sum = 0;
        rep(i,3)rep(k,3) sum += cube[i][2][k].val[4];
        ans.pb(sum);
        return;
    }
    int k = cur/9, i = cur/3%3, j = cur%3;
    dice d = (dice){2,5,6,1,3,4};
    rep(r,24){
        d.rotk();
        if(!(r%4)){
            if(r < 16) d.rotj();
            else if(r == 16) d.roti();
            else rep(_,2) d.roti();
        }
        if(k==0 and T[i][j] and T[i][j] != d.val[0]) continue;
        if(i==2 and F[k][j] and F[k][j] != d.val[2]) continue;
        if(i and cube[i-1][j][k].val[2]+d.val[3]!=7) continue;
        if(j and cube[i][j-1][k].val[4]+d.val[5]!=7) continue;
        if(k and cube[i][j][k-1].val[1]+d.val[0]!=7) continue;
        cube[i][j][k] = d;
        rec(cur+1);
    }
}

void solve(){
    ans.clear();
    memset(cube, 0, sizeof(cube));
    rec(0);
    if(ans.size()==0) {
        cout << 0 << endl;
        return;
    }
    sort(all(ans));
    ans.erase(unique(all(ans)),ans.end());
    rep(i,ans.size()) cout << ans[i] << (i==int(ans.size()-1)? '\n': ' ');
}

void input(){
    rep(i,3)rep(j,3) cin >> T[i][j];
    rep(i,3)rep(j,3) cin >> F[i][j];
}
signed main(){
    int __;
    cin >> __;
    while(__--){
        input();
        solve();
    }
    return 0;
}

Comments