Как решить эту мозаичную головоломку?

[Задача на 1000 очков на SRM 209, Div I]

На каком-то этапе проблема сводится к следующему:

Даны блоки из трех квадратных единиц, как показано ниже, которые можно вращать любым образом, сколькими способами можно заполнить прямоугольный блок заданного размера.

| x | x |
| x |

Например, для блока 3х4 есть 4 способа расположения этих блоков. Я ищу способ решить эту проблему, а не фактическое решение. Как мне найти количество способов. Есть так много способов, которыми это может произойти, и я также не вижу перекрывающихся подзадач для подхода DP.

Любые идеи приветствуются.


algorithm tiling
person Moeb    schedule 06.10.2012    source источник
comment
плитка - это проблема np, поэтому единственный способ - сгруппировать плитки по парам и попробовать каждую комбинацию блоков 3x2.   -  person Bartlomiej Lewandowski    schedule 06.10.2012
comment
Это точная проблема покрытия, и вы можете решить ее с помощью BDD с нулевым подавлением, не перечисляя все решения.   -  person harold    schedule 06.10.2012
comment
Я получаю 22025514 для 8x9, это правильно?   -  person harold    schedule 06.10.2012
comment
@harold: извините, я не уверен, какое решение для 8x9.   -  person Moeb    schedule 07.10.2012
comment
Знаете какие-нибудь нетривиальные результаты? И понятен ли мой подход? Я мог бы объяснить это немного подробнее, если хотите   -  person harold    schedule 07.10.2012
comment
В Topcoder есть редакционные статьи, описывающие решение каждой проблемы. Вы их проверяли?   -  person Anonym Mus    schedule 04.11.2012

Ответы (1)


arrow_upward
-1
arrow_downward

Все без исключения замощения блока pxq пространства L-образными тайлами сведутся к замощению блоками 2x3, состоящими из пар ваших L-образных тайлов. т.е. плитки либо в форме:

        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.

Таким образом, вы уже можете свести свою задачу к «паркетной» мозаике прямоугольника с прямоугольниками 2x3 и 3x2. Если, конечно, вы не занимаетесь плиткой неправильной непрямоугольной области — в этом случае вам придется рассматривать L-образные плитки индивидуально.

person Penguino    schedule 06.10.2012
comment
Это неправильно, т.е. 0011 | 0221 | 3324 | 3544 | 6557 | 6677. - person Nabb; 06.10.2012