UVa11391

UVa11391
メモ化する。
memo[BIT]で挑むとTLE喰らう。memo[C][R][BIT]にしよう。
テストデータが意地悪すぎる。何か面倒だった。

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()

typedef long long int lli;

using namespace std;

const int R = 4;
const int C = 4;

const int BIT = (1 << (C * R + 1));
int memo[C][R][BIT];

int no(int c, int r, int i, int j)
{
  return r * i + j;
}

int rec(int bit, int c, int r)
{
  if (memo[c - 1][r -1][bit] != -1) return memo[c - 1][r - 1][bit];
  if (__builtin_popcount(bit) == 1) return memo[c - 1][r - 1][bit] = 1;  

  int sum = 0;
  
  int di[] = {-1, -1, -1, 0, 0, 1, 1, 1};
  int dj[] = {-1, 0, 1, -1, 1, -1, 0, 1};

  for (int i = 0; i < c; ++i) {
    for (int j = 0; j < r; ++j) {
      if (bit & (1 << no(c, r, i, j))) ; else continue;
      for (int d = 0; d < 8; ++d) {
        int ni = i + di[d];
        int nj = j + dj[d];
        int mi = i + di[d] * 2;
        int mj = j + dj[d] * 2;

        if (mi < 0 || mj < 0) continue;
        if (c <= mi || r <= mj) continue;
        
        if (bit & (1 << no(c, r, ni, nj))) ; else continue;
        if (bit & (1 << no(c, r, mi, mj))) continue;
        
        int next = bit;
        next ^= 1 << no(c, r, i, j);
        next ^= 1 << no(c, r, ni, nj);
        next ^= 1 << no(c, r, mi, mj);
        sum += rec(next, c, r);
      }
    }
  }

  return memo[c - 1][r - 1][bit] = sum;
}

int main(int argc, char *argv[])
{
  fill(&memo[0][0][0], &memo[C - 1][R - 1][BIT], -1);

  int tc;
  scanf("%d\n", &tc);
  while (tc--) {
    int r, c, n;
    int bit = 0;
    scanf("%d %d %d\n", &r, &c, &n);
    while (n--) {
      int i, j;
      scanf("%d %d\n", &j, &i);
      --i;
      --j;
      bit |= 1 << no(c, r, i, j);
    }
    
    static int cnt = 0;
    printf("Case %d: %d\n", ++cnt, rec(bit, c, r));
  }
  return 0;
}