SRM417: CubeNets

これまた難しい問題だったけど、綺麗な解法を思い浮かんで気持ちよかった。

(問題概要)
立方体の展開図が文字列で与えられる。
立方体の展開図として正しいかどうか判断せよ。

(解法)
サイコロの展開図として考える。
展開図にそってサイコロを転がして、接地面の数字を割り当てていく。
このとき以下の矛盾がなければよい。

• 同じ数字が2箇所ある
• 同じ場所に2通りの数字の振り方がある

私のサイコロライブラリはゴリ押しなので汚いですがコード。

#include <cstdio>
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))

#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class CubeNets {
public:
  string isCubeNet(vector <string> figure);
};

class Dice{
public:
  enum direction{
    UP    = 0,
    RIGHT = 1,
    DOWN  = 2,
    LEFT  = 3,
    RRIGHT= 4,
    RLEFT = 5
  };

  /*
   *   6
   *   2
   * 3 1 4
   *   5
   */

private:
  static int next_top[7][7][6];
  static int next_right[7][7][6];
  static int front[7][7];

  int _top;
  int _right;

  static void initDie(){
    front[1][3] = 2; front[1][2] = 4; front[1][4] = 5; front[1][5] = 3;
    front[2][1] = 3; front[2][3] = 6; front[2][4] = 1; front[2][6] = 4;
    front[3][1] = 5; front[3][2] = 1; front[3][5] = 6; front[3][6] = 2;
    for(int i = 4; i < 7; i++){
      for(int j = 1; j < 7; j++){
        if(i == j || i + j == 7) continue;
        int t = 7 - i;
        int l = 7 - j;
        front[i][j] = front[t][l];
      }
    }

    for(int t = 1; t < 7; t++){
      for(int r = 1; r < 7; r++){
        if(t == r || t + r == 7) continue;

        next_top[t][r][UP]     = front[t][r];
        next_top[t][r][LEFT]   = r;
        next_top[t][r][RIGHT]  = 7 - r;
        next_top[t][r][DOWN]   = 7 - front[t][r];
        next_top[t][r][RRIGHT] = t;
        next_top[t][r][RLEFT]  = t;

        next_right[t][r][UP]     = r;
        next_right[t][r][LEFT]   = 7 - t;
        next_right[t][r][RIGHT]  = t;
        next_right[t][r][DOWN]   = r;
        next_right[t][r][RRIGHT] = 7 - front[t][r];
        next_right[t][r][RLEFT]  = front[t][r];
      }
    }
  }

  static void init(){
    static bool _init = false;

    if(!_init){
      initDie();
      _init = true;
    }
  }

public:
  Dice(int t = 1, int r = 3) : _top(t), _right(r) {
    init();
  }

  int getTop() const{ return _top; }
  int getRight() const{ return _right; }
  int getButtom() const{ return 7 - _top; }
  int getLeft() const{ return 7 - _right; }
  int getFront() const{ return front[_top][_right]; }
  int getBack() const{ return 7 - front[_top][_right]; }

  void next(int dir){
    int tmp = _top;
    _top     = next_top[_top][_right][dir];
    _right   = next_right[tmp][_right][dir];
  }

  void right() { next(RIGHT);  }
  void left()  { next(LEFT);   }
  void up()    { next(UP);     }
  void down()  { next(DOWN);   }
  void rright(){ next(RRIGHT); }
  void rleft() { next(RLEFT);  }

  static void forceInit(){ init(); }

  static int nextTop(int t, int r, int d){
    return next_top[t][r][d];
  }

  static int nextRight(int t, int r, int d){
    return next_right[t][r][d];
  }

};

int Dice::next_right[7][7][6] = {{{0}}};
int Dice::next_top[7][7][6]   = {{{0}}};
int Dice::front[7][7]         = {{0}};

bool solve(const vector<string> &f){
  const int h = f.size();
  const int w = f[0].size();
  vector<vector<int> > g(h, vector<int>(w));
  int sx, sy;

  REP(i, h){
    REP(j, w){
      if(f[i][j] == '#'){
	sx = j; sy = i;
	goto proc;
      }
    }
  }
 proc:;

  int cnt = 0;
  typedef pair<int, pair<int, Dice> > data;
  vector<int> use(7);
  queue<data> q;
  q.push(make_pair(sx, make_pair(sy, Dice())));

  while(q.size()){
    const data dt = q.front(); q.pop();
    const int x = dt.first;
    const int y = dt.second.first;
    const Dice d = dt.second.second;

    if(g[y][x] != 0){
      if(d.getButtom() != g[y][x])
	return false;
      else
	continue;
    }else{
      if(use[d.getButtom()]) return false;
      g[y][x] = d.getButtom();
      use[d.getButtom()] = 1;
      cnt++;
    }

    if(ISIN(x, y - 1, w, h) && f[y - 1][x] == '#'){
      Dice dd = d;
      dd.up();
      q.push(data(x, make_pair(y - 1, dd)));
    }

    if(ISIN(x, y + 1, w, h) && f[y + 1][x] == '#'){
      Dice dd = d;
      dd.down();
      q.push(data(x, make_pair(y + 1, dd)));
    }

    if(ISIN(x - 1, y, w, h) && f[y][x - 1] == '#'){
      Dice dd = d;
      dd.left();
      q.push(data(x - 1, make_pair(y, dd)));
    }

    if(ISIN(x + 1, y, w, h) && f[y][x + 1] == '#'){
      Dice dd = d;
      dd.right();
      q.push(data(x + 1, make_pair(y, dd)));
    }
  }

  return cnt == 6;
}

string CubeNets::isCubeNet(vector <string> figure){
  return solve(figure) ? "YES" : "NO";
}