Bu döşeme bulmacaya nasıl saldırılır? herhangi bir şekilde döndürülebilir olan, aşağıdaki gibi, üç kare birimlerin</p> <p>Verilen blok:

Question

[SRM 209 1000 nokta problemi, Div I] bir aşamada

sorun, aşağıdaki azaltır Belirli bir boyuttaki dikdörtgen bir bloğu doldurmak için kaç yol vardır. Örneğin, 3x4 blok için, bu blokları düzenlemek için 4 yol vardır. Bu soruna saldırmak için bir yol arıyorum, gerçek çözüm değil. Yolların sayısını bulmak için nasıl giderim. Bunun olabileceği pek çok yol var ve ben de bir DP yaklaşımı için örtüşen alt problemleri görmüyorum.

Herhangi bir anlayışa açığız.

Answer 1

İstisnasız, L-şekilli fayanslara sahip bir pxq boşluk bloğunun her bir fayansı, L-şekilli kiremit çiftlerinden oluşan 2x3 blokları ile fayansı azaltacaktır. Yani fayans şeklinde ya şunlardır:

 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. 

Yani zaten 2x3 ve 3x2 dikdörtgenler ile dikdörtgenin bir 'parquet'-döşeme için sorununuzu azaltabilir. Tabii ki, düzensiz dikdörtgen olmayan bir bölgeyi döşediğiniz sürece - bu durumda L-şekilli fayansları ayrı ayrı düşünmelisiniz.