1253 - Dice Puzzle

問題

さいころ27個を図のように並べる。このとき、合わさる面の数字同士の和は7になるようにする。
また、それを上から見たときの数字と前から見たときの数字が入力として与えられる。
ただし入力の数字が0ならばその位置の数字は何でもいい。
考えられる全てのさいころの並べ方に対して、右から見たときの数字の和を全て出力せよ。
出力は、昇順で重複しないようにする。

解法

DFSで枝狩り全探索。
制約が厳しいので結構早く終わる。
さいころは全部の向きを試せばよい。

出力の制約に
「The output may have spaces at ends of lines.」
という文があるのに、行の最後にスペースを入れるとPresentation Errorだった…。

ソース

template <class T>
struct dice {
  T t,b,n,s,e,w;              // top bottom north south east west
  dice() {}
  dice(T t, T b, T n, T s, T e, T w) : t(t),b(b),n(n),s(s),e(e),w(w) {}
  void roll(T &a, T &b, T &c, T &d) { swap(a,b); swap(b,c); swap(c,d); }
  void roll_x() { roll(t, n, b, s); }
  void roll_y() { roll(t, w, b, e); }
  void roll_z() { roll(s, e, n, w); }
  vector<dice> all_rolls() {
    vector<dice> ret;
    for (int k=0; k<6; (k&1?roll_y():roll_x()),++k)
      for (int i=0; i<4; roll_z(), ++i)
        ret.push_back(*this);
    return ret;
  }
};
 
dice<int> di[3][3][3];              // 手前の左上が原点、右向きX軸・下向きY軸・奥Z軸
int top[3][3];
int front[3][3];

set<int> ans;

void dfs(int x, int y, int z) {
  if (x == 3) { dfs(0,y+1,z); return; }
  if (y == 3) { dfs(0, 0, z+1); return; }
  if (z == 3) {
    int sum = 0; 
    REP(i, 3) REP(j, 3)
      sum += di[2][i][j].e;
    ans.insert(sum);
    return;
  }
  dice<int> d(1,6,5,2,3,4);
  vector<dice<int> > all = d.all_rolls();
  int res = 0;
  REP(i, all.size()) {
    if (z == 0 && front[y][x] && all[i].s != front[y][x]) continue;
    if (y == 0 && top[2-z][x] && all[i].t != top[2-z][x]) continue;
    if (x && di[x-1][y][z].e + all[i].w != 7) continue;
    if (y && di[x][y-1][z].b + all[i].t != 7) continue;
    if (z && di[x][y][z-1].n + all[i].s != 7) continue;
    di[x][y][z] = all[i];
    dfs(x+1,y,z);
  }
}

int main() {
  int N;
  cin >> N;
  while(N--) {
    REP(i, 3) REP(j, 3)
      cin >> top[i][j];
    REP(i, 3) REP(j, 3)
      cin >> front[i][j];
    ans.clear();
    dfs(0,0,0);
    if (ans.size()) {
      bool f = 0;
      FOR(it, ans) {
        if (f) cout << " ";
        else f = 1;
        cout << *it;
      }
      cout << endl;
    } else {
      cout << 0 << endl;
    }
  }
}