HOME
Даны Тетриминки - фигурки тетриса, состоящие из четырех блоков
Цель - разместить заданный набор тетриминок в квадратной области наименьшей площади так, чтобы тетриминки не пересекались друг с другом (незаполненные «дырки» в области допускаются).
Задача проекта является частным случаем Задачи о покрытии множества.
В нашем случае Задачу о покрытии множества можно переформулировать следующим образом:
- Есть множество
$S$ (искомое квадратное поле (возможно, с дырками, т.е. пустыми квадратиками)) - Есть набор подмножеств
$Y$ множества$S$ (всевозможные разрезания$S$ , включая отдельные квадратики 1x1, невалидные и валидные тетриминки,а также кусочки, содержащие иное (не четыре) число квадратиков) - Задача состоит в том, чтобы выбрать из
$Y$ такие элементы$Y'$ (тетриминки из заданного набора), что каждый элемент из$S$ (непустой квадратик) содержится только в одном из множеств, входящих в$Y'$ - То есть объединение всех множеств в
$Y'$ (тетриминки из заданного набора) составляет (покрывает) множество$S$ , и при этом в$Y'$ нет попарно пересекающихся множеств
В качестве алгоритма использовалась интерпретация Алгоритма Х Д.Кнута с использованием техники “танцующих ссылок”.
- Вначале нам нужно определить минимальный размер
$k$ стороны квадрата поля$S$ , в который алгоритм будет пытаться разместить заданные фигуры.
Размер стороны$k$ будет равен либо максимальной длине тетриминки по высоте или ширине, либо квадратному корню из * n$, где$n$ - число тетриминок, поданных на вход.
При этом значение квадратного корня берется с округлением в бОльшую сторону. Например, если на вход подается две тетраминки \times 4$ и \times 2$, то у поля будет размер \times 4$ (его определяет максимальная длина первой тетриминки), а если на вход поданы две тетриминки размером \times 2$, то первоначальный размер поля, куда алгоритм будет пытаться уместить тетриминки (увы, безуспешно), будет равен \times 3$, т.е.$\sqrt{4*2} = 3$ , с округлением в бОльшую сторону). - Затем алгоритм рекурсивно, в соответствии с требованиями задания (тетриминки должны располагаться в приоритетном порядке номера в исходном файле относительно левого верхнего угла поля
$S$ ), производит попытку замостить квадратное поле тетриминками. - В случае неудачи размер
$k$ каждой стороны поля$S$ увеличивается на единицу и процесс рекурсивного подбора покрытия квадрата$S$ тетриминками повторяется.
Ниже представлены примеры входных файлов с различными наборами тетриминок и результаты работы программы fillit:
- Восемь одинаковых вертикальных тетриминок размером
$4 \times 1$
- Четыре одинаковых "квадратных" тетриминки, размером
$2 \times 2$
- Четыре тетриминки различной конфигурации
- Еще один пример из четырех тетриминок различной конфигурации
