algorithm - 如何攻击这个拼图游戏？

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

在某个阶段，问题可以归结为以下几个方面:

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

| x | x |
| x |

例如，对于3x4的块，有4种排列这些块的方法。我正在寻找一种解决此问题的方法，而不是实际的解决方案。我如何找到方法的数量。发生的方式有很多，我也不认为DP方法会出现重叠的子问题。

欢迎有任何见识。

最佳答案

无一异常(exception)，每个带有L形图块的pxq空间块的平铺都将减少为2x3块的平铺，该图块由成对的L形图块组成。 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.

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

关于algorithm - 如何攻击这个拼图游戏？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12757602/