AOJ 1118 : Nets of Dice - 土下座しながら探索中

問題概要：
5*5のセルには0から6までの数字がかかれている
これがサイコロの展開図になっているかどうか判定せよ

解法：
小さいので実際にDFSで展開図になっているかどうか確かめる

まず最初に明らかに駄目なケースははじいておく
(連結でない、1から6までがちょうど１回ずつでてきていない場合)
あとは入力で与えられた図の０でないセルから実際にサイコロを動かしてみて、全ての０でないセルに到達できるかどうか判定する
図が逆さまであることもあるので、９０度回転 * 4 を入力で受け取ったままの状態とそれを反転させて状態について行い確かめる

DFSで確かめる際に、今いるセルの数字とサイコロのトップの値が同じであるようにしながら探索する
隣接する４つのセルに移動する場合には、ちゃんと正しい方向にある場合のみ移動する

コード：

//サイコロはSpagettie sourceのまんまなのでカット
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int IINF = INT_MAX;

vector<string> rotate90(const vector<string>& piece){
  vector<string> ret;
  int h = piece[0].size(), w = piece.size();
  ret.resize(h);
  for(int i=0;i<h;i++)ret[i].resize(w);
  for(int y=0;y<ret.size();y++){
    for(int x=0;x<ret[0].size();x++){
      ret[y][x] = piece[ret[0].size()-1-x][y];
    }
  }
  return ret;
}

// サイコロライブラリ


int T,itmp;
int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};
bool used[5][5];
int counter[6];

inline bool isValid(const vector<string>& vec,int x,int y){ return ( 0 <= x && x < vec[0].size() && 0 <= y && y < vec.size() ); }

void dfs(const vector<string> &vec,int x,int y){
  if( used[y][x] ) return;
  counter[vec[y][x]-'1']++;
  used[y][x] = true;
  rep(i,4) {
    int nx = x + dx[i], ny = y + dy[i];
    if( isValid(vec,nx,ny) ) {
      if( !used[ny][nx] && vec[ny][nx] != '0' ) { 
        dfs(vec,nx,ny);
      }
    }
  }
}



bool check(const vector<string> &vec){
  rep(i,5)rep(j,5) used[i][j] = false;
  rep(i,6) counter[i] = 0;

  rep(i,vec.size())rep(j,vec[i].size()) if( vec[i][j] != '0' ) {
    dfs(vec,j,i);
    goto Skip;
  }
 Skip:;

  rep(i,vec.size())rep(j,vec[i].size()) if( vec[i][j] != '0' && !used[i][j] ) return false;
  rep(i,6) if( counter[i] != 1 ) return false;
  return true;
}

const string YES = "true", NO = "false";
int top,dice_tmp,H,W;
bool error;
const bool DEBUG = false;

inline void roller(dice<int> &die,int type){
  if( type == 0 ) { // FRONT to TOP
    rep(i,3) die.roll_x();
  } else if( type == 1 ) { // LEFT to TOP
    die.roll_y();
  } else if( type == 2 ) { // BACK to TOP
    die.roll_x();
  } else { // RIGHT to TOP
    rep(i,3) die.roll_y();
  }
}

void dfs2(dice<int> &die,const vector<string>& vec,int x,int y){

  if( error ) return;
  if( used[y][x] ) return;
  used[y][x] = true;

  rep(i,4){
    int nx = x + dx[i], ny = y + dy[i];
    if( !isValid(vec,nx,ny) ) continue;
    if( vec[ny][nx] == '0' ) continue;
    if( die[dir[i]] != vec[ny][nx]-'1' ) {
      error = true;
      return;
    }
    roller(die,i);
    dfs2(die,vec,nx,ny);
    roller(die,(i+2)%4);
  }
}

bool correct(const vector<string>& vec){
  dice<int> die = makeDice(top,dice_tmp);
  int sx = -1, sy = -1;
  rep(i,vec.size())rep(j,vec[i].size()) if( vec[i][j]-'1' == top ) {
    sx = j, sy = i;
    break;
  }

  rep(i,4) {
    int nx = sx + dx[i], ny = sy + dy[i];
    if( !isValid(vec,nx,ny) ) continue;
    if( vec[ny][nx]-'1' == dice_tmp ) {
      int debug = 0;
      while( die[dir[i]] != dice_tmp ){
        die.roll_z();
        debug++;
      }
      break;
    }
  }

  H = vec.size(), W = vec[0].size();

  rep(i,H)rep(j,W)used[i][j]=false;
  error = false;
  dfs2(die,vec,sx,sy);
  if( error ) return false;
  rep(i,H)rep(j,W)if(vec[i][j]!='0'&&!used[i][j])return false;
  return true;
}

inline void simulate(vector<string> vec){
  rep(i,2){
    rep(_,4){
      if( correct(vec) ) {
        cout << YES << endl;
        return;
      }
      vec = rotate90(vec);
    }
    rep(j,vec.size()) reverse(vec[j].begin(),vec[j].end());
  }
  cout << NO << endl;
}

int main(){
  cin >> T;
  while( T-- ){
    vector<string> vec(5);
    rep(i,5) vec[i] = "";
    rep(i,5) rep(j,5) {
      cin >> itmp;
      vec[i] += string(1,(char)('0'+itmp));
    }

    if( !check(vec) ) {
      cout << NO << endl;
      continue;
    }

    top = -1,dice_tmp = -1;
    rep(i,vec.size())rep(j,vec[i].size())if(vec[i][j]!='0') {
      top = vec[i][j] - '1';
      rep(k,4){
        int nx = j + dx[k], ny = i + dy[k];
        if( isValid(vec,nx,ny) ) {
          if( vec[ny][nx] != '0' ) {
            dice_tmp = vec[ny][nx] - '1';
            goto Skip2;
          }
        } 
      }
    }
  Skip2:;
    assert( top != -1 && dice_tmp != -1 );

    simulate(vec);

  }
  return 0;
}