Làm thế nào để tấn công câu đố ốp lát này?

Question

[Vấn đề 1000 điểm trên SRM 209, Div I]

Tại một số giai đoạn, vấn đề giảm như sau:

khối Với ba đơn vị vuông, giống như dưới đây, mà có thể được luân chuyển trong bất cứ cách nào , có bao nhiêu cách để điền vào một khối hình chữ nhật có kích thước nhất định.

| x | x | 
| x | 

Ví dụ, đối với khối 3x4, có 4 cách sắp xếp các khối này. Tôi đang tìm kiếm một cách để tấn công vấn đề này, và không phải là giải pháp thực tế. Làm cách nào để tôi tìm ra số cách. Có rất nhiều cách mà nó có thể xảy ra, và tôi cũng không thấy các vấn đề phụ chồng lên nhau đối với phương pháp DP.

Mọi thông tin chi tiết đều được chào đón.

Answer 1

Không có ngoại lệ, mỗi lát gạch của khối pxq không gian với gạch hình chữ L, sẽ giảm xuống ốp lát với khối 2x3 bao gồm các lát hình chữ L của bạn. I E. các ô có dạng:

 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. 

Vì vậy, bạn đã có thể giảm sự cố với hình chữ nhật của hình chữ nhật với hình chữ nhật 2x3 và 3x2. Trừ khi, tất nhiên, bạn đang ốp lát một khu vực không hình chữ nhật không thường xuyên - trong trường hợp đó bạn phải xem xét các gạch hình chữ L cá nhân.