如何攻擊這個拼貼拼圖？

Question

[上SRM 209的1000點問題，分區I]

在某些階段，該問題簡化爲以下：

三個正方形單位給出的塊，如以下，其可以以任何方式旋轉，有多少種方式來填充給定大小的矩形塊。

| 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的矩形矩形的「parquet'碎片。當然，除非你正在拼貼一個不規則的非矩形區域 - 在這種情況下，你必須考慮L形瓷磚的個性。