论坛 › 欧拉计划（Project Euler） › 题目161：Triomino

欧拉计划 发表于 2016-9-14 23:04:11

题目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 发表于 2022-10-2 21:34:52

本帖最后由 guosl 于 2022-10-3 22:20 编辑

应用状态压缩的动态规划来做。
答案：20574308184277971
#include <iostream>
#include <cstring>
using namespace std;

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

stObj bobj;//最基本的六种形状
unsigned long long f;

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

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

查看完整版本: 题目161：Triomino