이 기와 퍼즐을 공격하는 방법은 무엇입니까? 임의의 방식으로 회전 될 수있는 다음과 같은 세 개의 사각형 단위</p> <p>감안 블록 :

Question

[SRM (209)의 1000 점에 문제가 본부 I 몇몇 단계에서

이 문제는 다음 줄여 주어진 크기의 직사각형 블록을 채울 수있는 방법은 여러 가지가 있습니다.

| 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 모양 타일을 개별적으로 고려해야합니다.