题目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

#include <iostream>
#include <cstring>
using namespace std;

struct stObj
{
  short L[3];//三层布局
  stObj(void)
  {
    memset(L, 0, 3 * sizeof(short));
  }
};

stObj bobj[6];//最基本的六种形状
unsigned long long f[13][512][512];

void dfs(int k, stObj oObj, stObj nObj, int c)//用深搜来找出扩充
{
  if (nObj.L[0] == 511)
  {
    f[k][nObj.L[1]][nObj.L[2]] += f[k - 1][oObj.L[0]][oObj.L[1]];//递推方程
    return;
  }
  if (c >= 9)
    return;
  if ((nObj.L[0] & (1 << c)) != 0)
    return dfs(k, oObj, nObj, c + 1);
  for (int i = 0; i < 6; ++i)//查找可以铺设的块
  {
    stObj tobj = bobj[i];
    int d = c;
    if ((tobj.L[0] & 1) == 0)
      --d;
    if (d < 0)
      continue;
    //对基本块进行平移
    tobj.L[0] = (tobj.L[0] << d);
    tobj.L[1] = (tobj.L[1] << d);
    tobj.L[2] = (tobj.L[2] << d);
    if ((tobj.L[0] & 512) != 0 || (tobj.L[1] & 512) != 0 || (tobj.L[2] & 512) != 0)//检查是否出头
      continue;
    if ((nObj.L[0] & tobj.L[0]) == 0 && (nObj.L[1] & tobj.L[1]) == 0 && (nObj.L[2] & tobj.L[2]) == 0)//检查是否有重叠
    {
      //铺下去
      stObj tt = nObj;
      tt.L[0] |= tobj.L[0];
      tt.L[1] |= tobj.L[1];
      tt.L[2] |= tobj.L[2];
      dfs(k, oObj, tt, c + 1);//查找新的块
    }
  }
}

int main(void)
{
  //形状一
  bobj[0].L[0] = 2;
  bobj[0].L[1] = 3;
  bobj[0].L[2] = 0;
  //形状二
  bobj[1].L[0] = 1;
  bobj[1].L[1] = 3;
  bobj[1].L[2] = 0;
  //形状三
  bobj[2].L[0] = 3;
  bobj[2].L[1] = 2;
  bobj[2].L[2] = 0;
  //形状四
  bobj[3].L[0] = 3;
  bobj[3].L[1] = 1;
  bobj[3].L[2] = 0;
  //形状五
  bobj[4].L[0] = 1;
  bobj[4].L[1] = 1;
  bobj[4].L[2] = 1;
  //形状六
  bobj[5].L[0] = 7;
  bobj[5].L[1] = 0;
  bobj[5].L[2] = 0;
  f[0][0][0] = 1;
  //下面部分是可以用OpenMP进行平行化处理的，不过本身耗时不多，就不做了
  for (int k = 1; k <= 12; ++k)
  {
    for (int i = 0; i < 512; ++i)
      f[k][i][0] += f[k - 1][511][i];
    for (int i = 0; i < 511; ++i)//枚举状态
    {
      for (int j = 0; j < 512; ++j)
      {
        stObj obj;
        obj.L[0] = i;
        obj.L[1] = j;
        dfs(k, obj, obj, 0);//递归铺设
      }
    }
  }
  cout << f[12][0][0] << endl;
  return 0;
}