Wie angreife ich dieses Fliesenpuzzle?

Question

[Der 1000 Punktproblem auf SRM 209, Div I]

Irgendwann reduziert sich das Problem auf die folgenden:

Bei Blöcken von drei Quadrateinheiten, wie unten, die in irgendeiner Art und Weise gedreht werden kann, , wie viele Wege gibt es, um einen rechteckigen Block gegebener Größe zu füllen.

| x | x | 
| x | 

Zum Beispiel gibt es für einen Block von 3x4 4 Möglichkeiten, diese Blöcke anzuordnen. Ich suche nach einer Möglichkeit, dieses Problem anzugehen, und nicht die tatsächliche Lösung. Wie finde ich die Anzahl der Wege? Es gibt so viele Möglichkeiten, dass es passieren kann, und ich sehe auch keine überlappenden Teilprobleme für einen DP-Ansatz.

Alle Einblicke sind willkommen.

Answer 1

Ausnahmslos wird jeder Tiling eines pxq-Blockes mit L-förmigen Kacheln auf Kacheln mit 2x3 Blöcken bestehend aus Paaren Ihrer L-förmigen Kacheln reduziert. I.e. Die Fliesen sind entweder in der Form:

 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. 

So können Sie bereits Ihr Problem eine ‚parquet'-Fliesen ein Rechteck mit 2x3 und 3x2 Rechtecke reduzieren. Es sei denn natürlich, Sie kacheln eine unregelmäßige nicht-rechteckige Region - in diesem Fall müssen Sie die L-förmigen Fliesen individuell betrachten.