このタイルパズルを攻撃する方法は？

Question

[SRM 209上の千点の問題、本部I]

いくつかの段階で、問題は、以下に減少：任意の方法で回転させることができる以下のような3つの平方単位の

考えるブロック与えられた大きさの矩形のブロックを何通りも埋める方法があります。

| 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. 

だから、あなたはすでに、2×3と3×2の長方形の長方形の「parquet'タイリングにあなたの問題を軽減することができます。もちろん、不規則な非長方形の領域をタイル張っている場合を除き、L字型のタイルを個別に考える必要があります。