Come attaccare questo puzzle di piastrellatura?

Question

[Il problema 1000 punti su SRM 209, Div I]

Ad un certo punto, il problema si riduce alla seguente:

blocchi Dato di tre unità quadrate, come qui di seguito, che può essere ruotato in modo , quanti modi ci sono per riempire un blocco rettangolare di dimensioni date.

| x | x | 
| x | 

Ad esempio, per un blocco di 3x4, ci sono 4 modi per disporre questi blocchi. Sto cercando un modo per attaccare questo problema, e non la soluzione reale. Come faccio a trovare il numero di modi. Ci sono così tanti modi in cui potrebbe accadere, e non vedo nemmeno sub problemi sovrapposti per un approccio DP.

Qualsiasi approfondimento è benvenuto.

Answer 1

Senza alcuna eccezione, ogni piastrellatura di un blocco di spazio pxq con tessere a forma di L ridurrà alla piastrellatura con 2x3 blocchi costituiti da coppie di piastrelle a forma di L. Cioè le piastrelle sono sia nella forma:

 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. 

Così si può già ridurre il problema ad un 'parquet'-piastrelle di un rettangolo con 2x3 e 3x2 rettangoli. A meno che, naturalmente, non si stia piastrellando una regione irregolare non rettangolare, nel qual caso si devono considerare le tessere a forma di L solo.