ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1116 Jigsaw Puzzles for Computers

概要

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1116


9つのジグソーパズルのピースがあり、それらを組み合わせてジグソーパズルを完成させます。
何通りの組み合わせ方があるかを求める問題です。

ピースは大文字と小文字の同じアルファベット組み合わせることができます。
(例)a = A, z = Z


解法

深さ優先探索(dfs)+枝刈りで解くことができます。

C++だと大文字⇒小文字の変換をtolower、小文字⇒大文字の変換をtoupperでできます。


ソースコード

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<complex>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<cstring>
#include<cassert>
using namespace std;
 
#define REP(i,x,n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i,n) REP(i, 0, n)
#define f first
#define s second
#define mp make_pair
#define pb push_back
 
typedef pair<int,int> P;
typedef long long ll;
 
static const int INF = (1<<29);
static const double EPS = 1e-9;
static const double PI = acos(-1.0);
static const int dy[]={-1,0,1,0};
static const int dx[]={0,1,0,-1};
 
struct Frame{
  char piece[4];
  Frame(){
    rep(i,4) piece[i] = ' ';
  }
  Frame(char *p){
    rep(i,4) piece[i] = p[i];
  }
};
 
int ans;
char puzzle[9][4];
bool used[9];
Frame frame[3][3];
 
void dfs(int count){
  if(count==9) ans++;
  else{
    int y = count / 3;
    int x = count % 3;
    rep(i,9){
      if(used[i]) continue;
      rep(j,4){ // rotate
        bool fit = true;
        char tmp[4];
        rep(k,4) tmp[k] = puzzle[i][(j+k)%4];
        rep(k,4){
          int ny = y + dy[k];
          int nx = x + dx[k];
          if(0<=nx&&nx<3 && 0<=ny&&ny<3){
            char a = tmp[k];
            char b = frame[ny][nx].piece[(k+2)%4];
            if(b==' ') continue;
            if(!((tolower(a)==b && a==toupper(b)) || (toupper(a)==b && a==tolower(b)))){
              fit = false;
              break;
            }
          }
        }
        if(fit){
          used[i] = true;
          frame[y][x] = Frame(tmp);
          dfs(count+1);
          frame[y][x] = Frame();
          used[i] = false;
        } 
      }
    }
  }
}
 
int main(){
  int N;
  cin >> N;
  while(N--){
    rep(i,3) rep(j,3) frame[i][j] = Frame();
    rep(i,9) rep(j,4) cin >> puzzle[i][j];
    ans = 0;
    memset(used,false,sizeof(used));
    dfs(0);
    cout << ans << endl;
  }
  return 0;
}