Задача про паркет

#алгоритм #комбинаторика #динамическое_программирование

Есть поле из клеток, размеры которого [n * m]. Необходимо покрыть это поле плитками
размера [1 * 2] (их можно поворачивать) таким образом, чтоб все клетки поля были накрыты,
и чтоб плитки не вылазили за границы поля. Задача состоит в том, чтоб найти количество
таких покрытий.

Данную задачу я решил с помощью динамики по профилю. Профиль - состояние одного столбца
поля. Подразумевается, что слева от данного профиля уже все клетки заполнены, а справа
ещё нет. Переход из профиля в профиль существует, если можно корректно положить некоторое
количество плиток (переходы хранятся в матрице dp).

Затем я считаю матрицу ответов:

if (dp[j][i]) ans[k][i] += ans[k - 1][j];


И после посчитанной матрицы ответов считаю ответ на задачу

if (isFinishing(i)) res += ans[m - 1][i];

Эта строчка означает, что если профиль может являться завершающим, то добавить это
число в ответу.

Данное решение вполне себе работает. Но затем я нашел модификацию данной задачи.
Модификация состоит в том, чтобы найти количество таких покрытий, в которых не будет
сплошных линий из плиток [1 * 2].

Пример: 

Первая картинка - это пример того, какими должны быть покрытия, вторая - какими не
должны. 

У меня был вариант хранить в динамике ещё состояние для каждой строки, была ли она
перекрыта хоть раз вертикальной плиткой, и добавлять к ответу только эти варианты.
Возможно, это бы и работало, но я не особо понимаю, как это реализовать. 

Подскажите, как реализовать, или предложите свои варианты решения.
    

Ответы

Ответ 1

Можно сделать динамически по рядам длины n. Для каждого промежуточного решения хранить
состояние "дырок", куда можно подставить вертикальные плитки. Установим, что мы всегда
движемся сверху вниз, значит дырки будут внизу. Динамический массив будет иметь вид: 

[int ряды, bool[] дырки] = кол-во решений


Например, все возможные решения для 1 ряда длиной 4:

[1, [0, 0, 1, 1]] = 1 // [xx] . .
[1, [1, 0, 0, 1]] = 1 // . [xx] .
[1, [1, 1, 0, 0]] = 1 // . . [xx]
[1, [1, 1, 1, 1]] = 1 // . .  . .


0 - горизонтальная плитка, 1 - пустое место для будущей вертикальной плитки. Количество
нулей идущих подряд всегда должно быть парным, все нули запрещены (что бы удовлетворить
ваше условие).

Дальше мы пытаемся соединить решение для x-1 рядов с решением для 1 ряда, что бы
получить решение для x рядов:

for (prev in solutions[x-1])
for (single in solutions[1])
{
    if (дырки prev совместимы c дырками single)
    {
        holes = считаем как будут выглядеть дырки после совмещения 2 решений
        solutions[x][holes] += prev;
    }
}


Конечным решением будет значение solutions[m, [0, 0, 0, 0, ... 0]], где все нули
- это полностью заполненный последний ряд.

Возможно существует более элегантное решение.