AOJ 1201 - Lattice Practices

問題概要

10枚の板があり、各板には5つの切り口があり、切り口は長いものと短いものがある。
5枚の板を切り口を上にして縦に並べ、その他の5枚の板を切り口を下にして横に並べ、縦の5枚の切り口にはめ込む。このとき、はめ込むことのできるパターン数(同じ組み合わせは除く)を求めよ。ただし、はめ込むためには切り口が長いものと短いもののペアでなければならない。また、板は180度回転して使っても良い。

(問題の図を見ると何やるか大体わかると思う。)

解法

枝刈り全探索。

コード

#include <bits/stdc++.h>

using namespace std;

string s[10],srev[10];
string H[5],W[5];
bool eq[10];

bool valid(int idx){
  for(int i = 0 ; i < 5 ; i++){
    if(W[idx][i] == H[i][idx]){
      return false;
    }
  }
  return true;
}

int solve(int idx,int S){
  if(S == (1<<10)-1){
    return 1;
  }
  int res = 0;
  for(int i = 0 ; i < 10 ; i++){
    if((S >> i) & 1) continue;
    if(idx < 5){
      H[idx] = s[i];
      res += solve(idx+1,S|(1<<i));
      if(!eq[i]){
        H[idx] = srev[i];
        res += solve(idx+1,S|(1<<i));
      }
    }else{
      W[idx-5] = s[i];
      if(valid(idx-5)){
        res += solve(idx+1,S|(1<<i));
      }
      if(!eq[i]){
        W[idx-5] = srev[i];
        if(valid(idx-5)){
          res += solve(idx+1,S|(1<<i));
        }
      }
    }
  }
  return res;
}

int main(){ 
  while(cin >> s[0], s[0] != "END"){
    memset(eq,false,sizeof(eq));
    string tmp = s[0];
    reverse(tmp.begin(),tmp.end());
    srev[0] = tmp;
    eq[0] = s[0] == srev[0];
    for(int i = 0 ; i < 9 ; i++){
      cin >> s[i+1];
      tmp = s[i+1];
      reverse(tmp.begin(),tmp.end());
      srev[i+1] = tmp;
      eq[i+1] = s[i+1] == srev[i+1];
    }
    cout << solve(0,0)/8 << endl;
  }
  return 0;
}