Теоретический материал

Задача о замощении домино

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

Для начала рассмотрим известную задачу: дана таблица n×m, нужно найти количество способов полностью замостить ее неперекрывающимися костяшками домино (прямоугольниками 2×1 и 1×2). Считаем n, m$ \le$10.

Заметим, что в процессе замощения каждая клетка таблицы будет иметь одно из двух состояний: покрыта какой-нибудь доминошкой или нет. Чтобы запомнить состояние клеток одного столбца, достаточно одной переменной P типа integer. Положим i-й бит P равным 1, если i-я сверху клетка данного столбца занята, 0 -- если свободна. Будем говорить в таком случае, что P -- битовая карта нашего столбца.

Теперь дадим определение базовой линии и профиля.

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

Можно занумеровать все базовые линии, по порядку слева направо, начиная с нуля. Таким образом, базовая линия с номером i -- это прямая, отсекающая первые i столбцов от всех остальных (если такие имеются).

Отныне через bi будем обозначать базовую линию с номером i.

Столбцы занумеруем так: слева от bi будет столбец с номером i. Другими словами, столбец с номером i находится между bi - 1 и bi.

 

 

Рисунок 1: Профиль будет таким: 1001012 = 1 + 4 + 32 = 37 (заняты первая + третья + шестая клетки).
\begin{figure}\centering {  \epsfbox{dprof/pic.1}}  \end{figure}

 

Профилем для базовой линии с номером i (bi) будем называть битовую карту для столбца с номером i при следующих дополнительных условиях:

 

1)
все клетки слева от bi - 1 уже покрыты;
2)
в i-м столбце нет вертикальных доминошек;
3)
считается, что справа от bi нет покрытых клеток.

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

 

 

Рисунок 2: p1 = 37,  p2 = 2; нетрудно заметить по рисунку, что из p1 можно получить p2. Таким образом, d[37, 2] = 1.
\begin{figure}\centering {  \epsfbox{dprof/pic.2}}  \end{figure}

 

Для каждого профиля p1 базовой линии bi определим множество профилей p2 базовой линии bi + 1, которые могут быть из него получены. На таблицу, соответствующую p1 (то есть все клетки слева от bi - 1 полностью покрыты, в i-м столбце клетки отмечены согласно p1), можно класть доминошки только двух типов:

 

1)
горизонтальные доминошки, которые пересекают bi (то есть делятся ей пополам);
2)
вертикальные доминошки, которые лежат слева от bi.

Также должны быть выполнены естественные дополнительные условия:

 

1)
новые доминошки не должны перекрываться друг с другом;
2)
они должны покрывать только незанятые клетки;
3)
каждая клетка i-го столбца должна быть покрыта.

Битовая карта столбца i + 1 и будет возможным профилем p2.

Очевидно, что полученный таким образом профиль p2 действительно удовлетворяет всем условиям, накладываемым на профиль.

Пусть d[p1, p2] - количество способов из профиля p1 (для bi) получить p2 (для bi + 1). Очевидно, для данной задачи про доминошки это число может быть только единицей или нулем. Различные задачи будут отличаться в основном только значениями d[p1, p2].

Заметим, что всего профилей 2n: от 00...02 = 0 до 11...12 = 2n - 1. Поэтому в данном случае матрица D будет иметь размер 2n×2n.

Пусть теперь a[i, p] -- количество способов таким образом расположить доминошки, что p -- профиль для bi (таким образом, все клетки левее bi - 1 покрыты).

Напишем рекуррентное соотношение.

 

  • Начальные значения (i = 1):
    a[1, 0] = 1;
    a[1, p2] = 0, p2 = 1, ..., 2n - 1

     

  • Общая формула (i > 1):

     

    a[i, p1] = $\displaystyle \sum_{p_2 = 0}^{2^n - 1}$a[i - 1, p2d[p2 p1] (2)

     

     

Заметим, что для базовой линии номер 1 существует единственный профиль (то есть битовая карта, удовлетворяющая условиям профиля) -- карта незаполненного столбца.

Ответ на вопрос задачи будет записан в a[m + 1, 0]. Ошибкой бы было считать правильным ответом число a[m, 2n - 1], так как в этом случае не учитывается возможность класть вертикальные доминошки в последнем столбце (см. второй пример).

Обсудим "странные" условия на доминошки при получении одного профиля из другого. Казалось бы, забыт еще один тип доминошек, которые могут участвовать при формировании нового профиля, а именно полностью лежащие в столбце i + 1. Дело в том, что если разрешить их, то некоторые способы замощения будут считаться более одного раза. Например, пусть n = 2, m = 2. Тогда d'[0][3] = 2, так как можно положить либо две вертикальные доминошки, либо две горизонтальные. Аналогично, d'[3][3] = 1 (можно положить одну вертикальную). В итоге

 

D' = $\displaystyle \left(\vphantom{  \begin{array}{ccccccc}  1 & 0 & 0 & 2 \\  0 & 0 & 1 & 0 \\  0 & 1 & 0 & 0 \\  1 & 0 & 0 & 1  \end{array}}\right.$$\displaystyle \begin{array}{ccccccc}  1 & 0 & 0 & 2 \\  0 & 0 & 1 & 0 \\  0 & 1 & 0 & 0 \\  1 & 0 & 0 & 1  \end{array}$$\displaystyle \left.\vphantom{  \begin{array}{ccccccc}  1 & 0 & 0 & 2 \\  0 & 0 & 1 & 0 \\  0 & 1 & 0 & 0 \\  1 & 0 & 0 & 1  \end{array}}\right)$,        A' = $\displaystyle \left(\vphantom{  \begin{array}{ccccc}  1 & 1 & 3 \\  0 & 0 & 0 \\  0 & 0 & 0 \\  0 & 1 & 2  \end{array}}\right.$$\displaystyle \begin{array}{ccccc}  1 & 1 & 3 \\  0 & 0 & 0 \\  0 & 0 & 0 \\  0 & 1 & 2  \end{array}$$\displaystyle \left.\vphantom{  \begin{array}{ccccc}  1 & 1 & 3 \\  0 & 0 & 0 \\  0 & 0 & 0 \\  0 & 1 & 2  \end{array}}\right)$

 

Имеем неправильный ответ 3 (можно посчитать вручную, что на самом деле ответ 2).

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

Упражнение. Доказать, что a[i, p] вычисляется правильно.

Вот какими будут D и A если n = 2, m = 4:

 

D = $\displaystyle \left(\vphantom{  \begin{array}{ccccccc}  1 & 0 & 0 & 1 \\  0 & 0 & 1 & 0 \\  0 & 1 & 0 & 0 \\  1 & 0 & 0 & 0  \end{array}}\right.$$\displaystyle \begin{array}{ccccccc}  1 & 0 & 0 & 1 \\  0 & 0 & 1 & 0 \\  0 & 1 & 0 & 0 \\  1 & 0 & 0 & 0  \end{array}$$\displaystyle \left.\vphantom{  \begin{array}{ccccccc}  1 & 0 & 0 & 1 \\  0 & 0 & 1 & 0 \\  0 & 1 & 0 & 0 \\  1 & 0 & 0 & 0  \end{array}}\right)$,        A = $\displaystyle \left(\vphantom{  \begin{array}{ccccccccc}  1 & 1 & 2 & 3 & 5 \\  ...  ...0 & 0 & 0 & 0 \\  0 & 0 & 0 & 0 & 0 \\  0 & 1 & 1 & 2 & 3  \end{array}}\right.$$\displaystyle \begin{array}{ccccccccc}  1 & 1 & 2 & 3 & 5 \\  0 & 0 & 0 & 0 & 0 \\  0 & 0 & 0 & 0 & 0 \\  0 & 1 & 1 & 2 & 3  \end{array}$$\displaystyle \left.\vphantom{  \begin{array}{ccccccccc}  1 & 1 & 2 & 3 & 5 \\  ...  ...0 & 0 & 0 & 0 \\  0 & 0 & 0 & 0 & 0 \\  0 & 1 & 1 & 2 & 3  \end{array}}\right)$

 

Таким образом, замостить доминошками таблицу 2×4 можно 5 способами, а таблицу 2×2 -- двумя. Если смотреть a[m, 2n - 1], то получим 2 и 1. Очевидно, что таблицу 2×2 можно замостить двумя, а не одним способом: пропущен вариант, когда кладутся две вертикальные доминошки. В случае 2×4 пропущены три замощения -- все случаи, когда последний столбец покрыт вертикальной доминошкой.

Существует два способа для вычисления D. Первый заключается в том, чтобы для каждой пары профилей p1 и p2 проверять, можно ли из p1 получить p2 описанным способом.

При втором способе для каждого профиля p1 пытаемся его замостить, кладя при этом только домоношки разрешенных двух типов. Для всех профилей p2 (и только для них), которые при этом получались в следующем столбце, положим d[p1, p2]=1. В большинстве случаев этот способ более экономичный, так что логично использовать именно его.

Ниже приведен код рекурсивной процедуры, которая заполняет строку d[p], то есть находит все профили, которые можно получить из p:

 

procedure go(p, profile, len : integer);
begin
                                                // n - из условия задачи
                                                // profile - текущий профиль
                                                // len - длина profile
     if (len = n) then begin                    // как только profile получился длины n, выходим
        d[p][profile] := 1;
        exit;
    end;     
    if (bit(p, len) = 0) then begin             // текущая ячейка в p (с номером len + 1) не занята
        go(p, profile + (1 shl len), len + 1);  // положили горизонтальную доминошку
        if (len < n - 1) then
            if (bit(p, len + 1) = 0) then begin // не занята еще и следующая ячейка
                go(p, profile, len + 2);        // положили вертикальную доминошку
            end;     
        end else begin
            go(p, profile, len + 1);            // текущая ячейка занята, ничего положить не можем
        end;
    end;

procedure determine_D; 
var p : integer; 
begin   
    for p := 0 to (1 shl n) - 1 do
        go(p, 0, 0);                            // запускать надо именно с такими параметрами 
end; 

Алгоритм вычисления D и A работает за

O(22n) (вычисление D) + O(22nm) (вычисление A) = O(22nm).