8

Есть поле из клеток, размеры которого [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].

Пример: введите сюда описание изображения

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

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

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

3
  • Кнут занимается подобными задачами в "Искусстве программирования", т. 4А, раздел 7.1.4 (начиная со стр. 295 русского издания; еще см. задача 7.1.4.215. Правда, у него другие методы :)
    – Harry
    Commented 21 окт. 2017 в 14:00
  • Слева от профиля клетки заполнены, справа пустые, а в самом профиле какие-то заполнены, а какие-то пустые?
    – user239133
    Commented 21 окт. 2017 в 14:12
  • "в которых не будет сплошных линий из плиток" - по идее, левая картинка тоже не прокатывает, т.к. плитки расположенные вдоль своих широких сторон - тоже образуют линию.
    – Kromster
    Commented 22 окт. 2017 в 6:40

1 ответ 1

4

Можно сделать динамически по рядам длины 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]], где все нули - это полностью заполненный последний ряд.

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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.