algorithm - 如何攻击这个拼图难题？

Question

[SRM 209 上的 1000 分问题，第一部分]

在某个阶段，问题归结为以下几点：

给定三个正方形单元的块，如下所示，可以以任何方式旋转，有多少种方式可以填充给定大小的矩形块。

| x | x |
| x |

例如，对于 3x4 的块，有 4 种排列这些块的方式。我正在寻找一种方法来解决这个问题，而不是实际的解决方案。我该如何寻找方法的数量。它可能发生的方式有很多，而且我也没有看到 DP 方法的重叠子问题。

欢迎任何见解。

Answer 1

无一例外，每一个 pxq 空间块与 L 形瓷砖的平铺，都将减少为 2x3 块的平铺，由一对 L 形平铺组成。即瓷砖要么采用以下形式：

        xx      xx
        xy  or  yx  to form a vertical 2x3 block or
        yy      yy

        xyy       xxy
        xxy  or   xyy  to form a horizontal 3,2 block.

因此，您已经可以将您的问题简化为 2x3 和 3x2 矩形的“镶木地板”平铺。当然，除非您正在平铺不规则的非矩形区域 - 在这种情况下，您必须单独考虑 L 形瓷砖。