UVa11391

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

view plainprint?

1. #include <iostream>  
2. #include <algorithm>  
3. #include <vector>  
4. #include <set>  
5. #include <map>  
6. #include <queue>  
7. #include <stack>  
8.   
9. #include <cstdio>  
10. #include <cstring>  
11. #include <cstdlib>  
12. #include <cmath>  
13.   
14. #define REP(i, n) for(int i=0; i<(int)n; ++i)  
15. #define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)  
16. #define ALL(c) (c).begin(),(c).end()  
17.   
18. typedef long long int lli;  
19.   
20. using namespace std;  
21.   
22. const int R = 4;  
23. const int C = 4;  
24.   
25. const int BIT = (1 << (C * R + 1));  
26. int memo[C][R][BIT];  
27.   
28. int no(int c, int r, int i, int j)  
29. {  
30.   return r * i + j;  
31. }  
32.   
33. int rec(int bit, int c, int r)  
34. {  
35.   if (memo[c - 1][r -1][bit] != -1) return memo[c - 1][r - 1][bit];  
36.   if (__builtin_popcount(bit) == 1) return memo[c - 1][r - 1][bit] = 1;    
37.   
38.   int sum = 0;  
39.     
40.   int di[] = {-1, -1, -1, 0, 0, 1, 1, 1};  
41.   int dj[] = {-1, 0, 1, -1, 1, -1, 0, 1};  
42.   
43.   for (int i = 0; i < c; ++i) {  
44.     for (int j = 0; j < r; ++j) {  
45.       if (bit & (1 << no(c, r, i, j))) ; else continue;  
46.       for (int d = 0; d < 8; ++d) {  
47.         int ni = i + di[d];  
48.         int nj = j + dj[d];  
49.         int mi = i + di[d] * 2;  
50.         int mj = j + dj[d] * 2;  
51.   
52.         if (mi < 0 || mj < 0) continue;  
53.         if (c <= mi || r <= mj) continue;  
54.           
55.         if (bit & (1 << no(c, r, ni, nj))) ; else continue;  
56.         if (bit & (1 << no(c, r, mi, mj))) continue;  
57.           
58.         int next = bit;  
59.         next ^= 1 << no(c, r, i, j);  
60.         next ^= 1 << no(c, r, ni, nj);  
61.         next ^= 1 << no(c, r, mi, mj);  
62.         sum += rec(next, c, r);  
63.       }  
64.     }  
65.   }  
66.   
67.   return memo[c - 1][r - 1][bit] = sum;  
68. }  
69.   
70. int main(int argc, char *argv[])  
71. {  
72.   fill(&memo[0][0][0], &memo[C - 1][R - 1][BIT], -1);  
73.   
74.   int tc;  
75.   scanf("%d\n", &tc);  
76.   while (tc--) {  
77.     int r, c, n;  
78.     int bit = 0;  
79.     scanf("%d %d %d\n", &r, &c, &n);  
80.     while (n--) {  
81.       int i, j;  
82.       scanf("%d %d\n", &j, &i);  
83.       --i;  
84.       --j;  
85.       bit |= 1 << no(c, r, i, j);  
86.     }  
87.       
88.     static int cnt = 0;  
89.     printf("Case %d: %d\n", ++cnt, rec(bit, c, r));  
90.   }  
91.   return 0;  
92. }  

#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;
}