题目161：Triomino

欧拉计划

Triominoes

A triomino is a shape consisting of three squares joined via the edges. There are two basic forms:

If all possible orientations are taken into account there are six:

Any n by m grid for which nxm is divisible by 3 can be tiled with triominoes.
If we consider tilings that can be obtained by reflection or rotation from another tiling as different there are 41 ways a 2 by 9 grid can be tiled with triominoes:

In how many ways can a 9 by 12 grid be tiled in this way by triominoes?

题目：

triomino是一个边相连的三个方块组成的图形，有下面两种基本的组成方式：

如果所有可能的方向都算进来的话，则有六种：

任何一个 n*m 的网格都可以用 triominoe 形状的图形覆盖，只要 n*m 能被 3 整除。

如果从一个填涂旋转或翻转得到的填涂都算作一个不同的填涂的话，那么，总计可以有以下 41 种方式用 triominoe 填涂一个 2×9 的网格：

请问，用上面的方法进行填涂的话，9×12 的网格可以有多少种填涂的方法？

guosl

应用状态压缩的动态规划来做。
答案：20574308184277971

1. #include <iostream>
   
2. #include <cstring>
   
3. using namespace std;
   
4. 
   
5. struct stObj
   
6. {
   
7.   short L[3];//三层布局
   
8.   stObj(void)
   
9.   {
   
10.     memset(L, 0, 3 * sizeof(short));
    
11.   }
    
12. };
    
13. 
    
14. stObj bobj[6];//最基本的六种形状
    
15. unsigned long long f[13][512][512];
    
16. 
    
17. void dfs(int k, stObj oObj, stObj nObj, int c)//用深搜来找出扩充
    
18. {
    
19.   if (nObj.L[0] == 511)
    
20.   {
    
21.     f[k][nObj.L[1]][nObj.L[2]] += f[k - 1][oObj.L[0]][oObj.L[1]];//递推方程
    
22.     return;
    
23.   }
    
24.   if (c >= 9)
    
25.     return;
    
26.   if ((nObj.L[0] & (1 << c)) != 0)
    
27.     return dfs(k, oObj, nObj, c + 1);
    
28.   for (int i = 0; i < 6; ++i)//查找可以铺设的块
    
29.   {
    
30.     stObj tobj = bobj[i];
    
31.     int d = c;
    
32.     if ((tobj.L[0] & 1) == 0)
    
33.       --d;
    
34.     if (d < 0)
    
35.       continue;
    
36.     //对基本块进行平移
    
37.     tobj.L[0] = (tobj.L[0] << d);
    
38.     tobj.L[1] = (tobj.L[1] << d);
    
39.     tobj.L[2] = (tobj.L[2] << d);
    
40.     if ((tobj.L[0] & 512) != 0 || (tobj.L[1] & 512) != 0 || (tobj.L[2] & 512) != 0)//检查是否出头
    
41.       continue;
    
42.     if ((nObj.L[0] & tobj.L[0]) == 0 && (nObj.L[1] & tobj.L[1]) == 0 && (nObj.L[2] & tobj.L[2]) == 0)//检查是否有重叠
    
43.     {
    
44.       //铺下去
    
45.       stObj tt = nObj;
    
46.       tt.L[0] |= tobj.L[0];
    
47.       tt.L[1] |= tobj.L[1];
    
48.       tt.L[2] |= tobj.L[2];
    
49.       dfs(k, oObj, tt, c + 1);//查找新的块
    
50.     }
    
51.   }
    
52. }
    
53. 
    
54. int main(void)
    
55. {
    
56.   //形状一
    
57.   bobj[0].L[0] = 2;
    
58.   bobj[0].L[1] = 3;
    
59.   bobj[0].L[2] = 0;
    
60.   //形状二
    
61.   bobj[1].L[0] = 1;
    
62.   bobj[1].L[1] = 3;
    
63.   bobj[1].L[2] = 0;
    
64.   //形状三
    
65.   bobj[2].L[0] = 3;
    
66.   bobj[2].L[1] = 2;
    
67.   bobj[2].L[2] = 0;
    
68.   //形状四
    
69.   bobj[3].L[0] = 3;
    
70.   bobj[3].L[1] = 1;
    
71.   bobj[3].L[2] = 0;
    
72.   //形状五
    
73.   bobj[4].L[0] = 1;
    
74.   bobj[4].L[1] = 1;
    
75.   bobj[4].L[2] = 1;
    
76.   //形状六
    
77.   bobj[5].L[0] = 7;
    
78.   bobj[5].L[1] = 0;
    
79.   bobj[5].L[2] = 0;
    
80.   f[0][0][0] = 1;
    
81.   //下面部分是可以用OpenMP进行平行化处理的，不过本身耗时不多，就不做了
    
82.   for (int k = 1; k <= 12; ++k)
    
83.   {
    
84.     for (int i = 0; i < 512; ++i)
    
85.       f[k][i][0] += f[k - 1][511][i];
    
86.     for (int i = 0; i < 511; ++i)//枚举状态
    
87.     {
    
88.       for (int j = 0; j < 512; ++j)
    
89.       {
    
90.         stObj obj;
    
91.         obj.L[0] = i;
    
92.         obj.L[1] = j;
    
93.         dfs(k, obj, obj, 0);//递归铺设
    
94.       }
    
95.     }
    
96.   }
    
97.   cout << f[12][0][0] << endl;
    
98.   return 0;
    
99. }

复制代码