algorithm - 如何解决这个拼图难题？

Question

[SRM 209, Div I 的 1000 分问题]

在某个阶段，问题会简化为以下内容:

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

| x | x |
| x |

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

欢迎任何见解。

Answer 1

无一异常(exception)，每次用 L 形瓷砖拼贴 pxq 空间 block 时，都会减少为由成对的 L 形瓷砖组成的 2x3 block 拼贴。 IE。瓷砖的形式是:

        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.

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