Расчет количества замощений прямоугольника меньшими прямоугольниками?

Question

[ewb]

Здравствуйте!
Пусть у нас есть большой прямоугольник.
Так же есть безлимитная куча маленьких одинаковых прямоугольников, с соотношением сторон 2:1, например 100x50.

Нужно рассчитать и и зафиксировать все способы замощения большого прямоугольника маленькими, так что бы они не выходили за грани большого и были плотно прижаты друг к другу.

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

Картинку прикрепляю (для примера два варианта замощения).


Какие алогоритмы для этого существуют? В какую сторону смотреть?

Answer 1

[Mrrl]

Здесь достаточно перебора с помощью рекурсии.
Вам нужно заполнить прямоугольник M*N плитками размером 1*2.
Берёте массив A[M,N], заполняете его нулями.
Вызываете функцию Fill(A,1).
Fill(A,k){
Ищете первый элемент A[p,q], равный нулю.
Если не нашли - массив заполнен, печатаете его. return.
Если элемент A[p+1,q] существует и равен нулю, то в прямоугольник можно положить горизонтальную плитку: в A[p,q] и A[p+1,q] кладёте число k, вызываете Fill(A,k+1). Обнуляете A[p,q] и A[p+1,q].
Если элемент A[p,q+1] существует и равен нулю, то в прямоугольник можно положить вертикальную плитку: в A[p,q] и A[p,q+1] кладёте число k, вызываете Fill(A,k+1). Обнуляете A[p,q] и A[p,q+1].
}
Если бы надо было считать число способов заполнения, надо было бы смотреть в сторону динамического программирования.

Comments

[ewb]

Ну речь как раз о количестве способов заполнения

[Mrrl]

ewb: А что же тогда значит "рассчитать и зафиксировать"? При подсчёте количества способов сами эти способы вы не увидите.
А количество считается так.
Будем считать, что горизонтальная сторона прямоугольника короче вертикальной. Рассмотрим конфигурации, обладающие следующими свойствами:
- нижние k-1 рядов полностью заполнены
- в k-м ряду заполнены клетки b1,b2,..,br (обозначим их множество S)
- в k-м ряду нет ни одной горизонтальной плитки
- все ряды выше k-го пустые.
Нам надо для каждой пары (k,S) посчитать количество допустимых способов P(k,S) заполнения этой фигуры. Для этого для любой пары множеств (S1,S2) считаем число способов R(S1,S2), которыми конфигурацию из (k,S1) можно превратить в (k+1,S2). Это число не зависит от k.
Например, если прямоугольник имеет ширину 3, то
R({},{1})=R({},{3})=R({},{1,2,3}=1
R({1},{})=R({1},{2,3})=1
R({2},{1,3})=1
R({3},{})=R({3},{1,2})=1
R({1,2},{3})=R({1,3},{2})=R({2,3},{1})=1
R({1,2,3},{})=1
Для остальных пар множеств R(S1,S2)=0.
Исходно у нас есть P(1,{})=1. Надо найти P(H+1,{}), где H - высота прямоугольника. Для этого перебираем k от 1 до H, и зная P(k,S) для всех S, находим P(k+1,S) опять же для всех S. Или просто возводим матрицу перехода в степень H.

[ewb]

Спасибо вам! Буду вникать!