如何攻击这个拼贴拼图？

Question

[SRM 209,Div I上的1000点问题]

在某个阶段,问题减少到以下几点:

给定三个方块的块,如下所示,可以以任何方式旋转,有多少种方法可以填充给定大小的矩形块.

| x | x |
| x |

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

任何见解都是受欢迎的.

Answer 1

无一例外，使用 L 形瓷砖对 pxq 空间块进行平铺时，将减少为使用由成对 L 形瓷砖组成的 2x3 块进行平铺。即图块的形式为：

        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 形瓷砖。