AOJ : 1103 - Board Arrangements for Concentration Games

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1103

8種類のカードが2枚ずつあり、これらのカードを縦４枚横４枚になるように、並べます。
ある種類のカード2枚を置くときは、入力によって与えられる四種類の位置関係の内、どれかを満たすように並べなければいけません。
そのようなルールを満たすように、全てのカードを並べるには、全部で何通りあるかを答えるのがこの問題です。

アルゴリズム

全探索するだけです。
再帰で2枚ずつカードを置いていって、カードを全て使い果たしたらカウント。

プログラム

#include <stdio.h>
#include <string.h>

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

int dx[4],dy[4];
int t[4][4];

int solve(int rem){
  int i;
  int x,y,nx,ny;
  int res = 0;

  if(rem == 0) return 1;

  //1枚目の場所を探す
  rep(y,4){
    rep(x,4) if(!t[y][x]) break;
    if(x != 4) break;
  }

  t[y][x] = 1;

  //2枚目の場所を決めて,再帰
  rep(i,4){
    nx = x + dx[i];
    ny = y + dy[i];
    if(nx>=0 && nx<4 && ny>=0 && ny<4 && !t[ny][nx]){
      t[ny][nx] = 1;
      res += solve(rem-1);
      t[ny][nx] = 0;
    }
  }

  t[y][x] = 0;

  return res;
}

int main(void){
  int i;

  while(1){
    rep(i,4) if(scanf("%d%d",&dx[i],&dy[i]) != 2) return 0;
    memset(t,0,sizeof(t));
    printf("%d\n",solve(8));
  }
}