¿Cómo atacar este rompecabezas de mosaico?

Question

[El problema 1000 punto de SRM 209, Div I]

En algún momento, el problema se reduce a lo siguiente:

bloques determinado de tres unidades cuadradas, como a continuación, que se puede girar de cualquier manera , cuántas formas hay para llenar un bloque rectangular de un tamaño dado.

| x | x | 
| x | 

Por ejemplo, para un bloque de 3x4, hay 4 formas de organizar estos bloques. Estoy buscando una forma de atacar este problema, y ​​no la solución real. ¿Cómo hago para encontrar la cantidad de formas? Hay muchas maneras en que podría suceder, y tampoco veo subproblemas superpuestos para un enfoque DP.

Cualquier idea es bienvenida.

Answer 1

Sin excepción, cada mosaico de un bloque de espacio de pxq con mosaicos en forma de L se reducirá a mosaico con bloques de 2x3 que consisten en pares de mosaicos en forma de L. Es decir. los azulejos son ya sea en la 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. 

Así que ya pueden reducir el problema a una 'parquet'-alicatado de un rectángulo con 2x3 y 3x2 rectángulos. A menos que, por supuesto, esté tejiendo una región irregular no rectangular, en cuyo caso debe considerar individualmente las fichas en forma de L.