Напишите программу или функцию, которая при положительных значениях n и m рассчитывает количество действительных различных элементов домино, которые вы можете поместить в прямоугольник размером n на m . Это последовательность A099390 в онлайн-энциклопедии целочисленных последовательностей . Вы можете принимать входные данные как аргумент (ы) функции, CLA или stdin, в любом приемлемом формате. Вы должны вернуть или вывести одно целое число в качестве вывода.

Каждая плитка не должна оставлять пробелов, и учитывается каждая отдельная плитка, включая повороты, отражения и т. Д. Например, плитки для 2x3:

|--    |||    --| 
|--    |||    --|

Пример входов / выходов:

1,  9 -> 0
2,  2 -> 2
2,  3 -> 3
4,  4 -> 36
4,  6 -> 281
6,  6 -> 6728
7, 10 -> 53175517

Ваша программа теоретически должна работать для любых n и m , но если вашей программе требуется слишком много памяти или ваш тип данных переполняется, это оправдано. Однако ваша программа должна работать правильно для любых n, m <= 8.

Самый короткий код в байтах побеждает.

Pyth, 30 29 байт

L?bsmy-tb]dfq1.a-VThbb1y*FUMQ

Попробуйте онлайн: демонстрация / тестовый пакет

Все примеры ввода выполняются в онлайн-компиляторе. Последний занимает несколько секунд.

Объяснение:

В моем коде я определю рекурсивную функцию y. Функция yберет список 2D-координат и возвращает количество различных элементов домино, используя эти координаты. Например y([[0,0], [0,1]]) = 1(одно горизонтальное домино), y([[0,0], [1,1]]) = 0(координаты не являются соседними) и y([[0,0], [0,1], [1,0], [1,1]]) = 2(два горизонтальных или два вертикальных домино). После определения функции я буду называть его со всеми координатами [x,y]с x in [0, 1, m-1], y in [0, 1, n-1].

Как работает рекурсивная функция? Это довольно просто. Если список координат пуст, существует ровно один допустимый лист и yвозвращается 1.

В противном случае я беру первую координату в списке b[0]и ищу остальные координаты соседей. Если соседа нет b[0], тогда нет возможности тайлинга, поэтому я возвращаю 0. Если есть один или несколько соседей, тогда количество тайлингов равно (числу тайлингов, где я соединяюсь b[0]с первым соседом через домину, плюс количество тайлингов, где я соединяюсь b[0]со вторым соседом, плюс ...) Поэтому я вызываю функцию рекурсивно для каждого соседа с сокращенным списком (удаляя две координаты b[0]и соседа). После этого я подвожу все результаты и возвращаю их.

Из-за порядка координат всегда возможны только два соседа: один справа и один ниже. Но мой алгоритм не заботится об этом.

                          UMQ  convert the input numbers into ranges
                        *F     Cartesian product (coords of each square)
L                              define a function y(b):
 ?b                              if len(b) > 0:
           f         b             filter b for squares T, which satisfy:
              .a-VThb                Euclidean distance between T and b[0]
            q1                       is equal to 1 (direct neighbors)
    m                              map each neighbor d to:
      -tb]d                          remove d from b[1]
     y                               and call recursively y with the rest
   s                               sum all those values and return them
                                 else:
                      1            return 1 (valid domino tiling found)
                       y*FUMQ  Call y with all coords and print the result  

Матлаб, 292

Я уверен, что это можно сократить, просто перенеся его на другой язык.

Основная идея - брутфорс: я придумал перечисление всех способов размещения m*n/2кирпичей домино на m*nдоске. Но это перечисление также включает в себя множество недопустимых значений (кирпичи, которые перекрывают или выходят за пределы доски). Таким образом, программа создает все эти значения и учитывает только действительные значения. Сложность выполнения составляет около O(2^(m*n/2) * m*n). Память не является проблемой, так 8x8как ей нужна только O(m*n)память. Но необходимое время 8x8составляет около 20 дней.

Здесь полностью прокомментированная версия, которая объясняет, что происходит.

PS: Если кто-нибудь знает, как заставить работать подсветку синтаксиса Matlab, включите соответствующий тег в этот ответ!

function C=f(m,n)
d = ceil(m*n/2);%number of dominoes
%enumeration: %the nth bit in the enumeration says whether the nth 
% domino pice is upright or not. we enumerate like this:
% firt piece goes top left:
% next piece goes to the left most column that has an empty spot, in the
% top most empty spot of that column
C=0;%counter of all valid tilings
for e=0:2^d-1 %go throu all enumerations
    %check whether each enumeration is valid
    A = ones(m,n);
    %empty spots are filled with 1
    %filled spots are 0 (or if overlapping <0) 
    v=1;%flag for the validity. hte grid is assumed to be valid until proven otherwise
    for i=1:d %go throu all pieces, place them in A
        %find the column where to place:
        c=find(sum(A)>0,1);
        %find the row where to place:
        r=find(A(:,c)>0,1);
        %find direction of piece:
        b=de2bi(e,d);
        if b(i)
            x=0;y=1;
        else
            x=1;y=0;
        end
        %fill in the piece:
        try
            A(r:r+y,c:c+x)=A(r:r+y,c:c+x)-1;
        catch z
            v=0;break;
        end
        %check whether A has no overlapping pieces
        if any(A(:)<0)
            v=0;break;
        end
    end
    %if valid, count it as valid
    if v && ~norm(A(:))
        disp(A)
        C=C+1;
    end
end

Здесь полностью игра в гольф:

function C=f(m,n);m=4;n=6;d=ceil(m*n/2);C=0;for e=0:2^d-1;A=ones(m,n);v=1;for i=1:d;c=find(sum(A)>0,1);r=find(A(:,c)>0,1);b=de2bi(e,d);if b(i);x=0;y=1;else;x=1;y=0;end;try;A(r:r+y,c:c+x)=A(r:r+y,c:c+x)-1;catch z;v=0;break;end;if any(A(:)<0);v=0;break;end;end;if v && ~norm(A(:));C=C+1;end;end

C89, 230 байт

f(n,m,b)int*b;{int s,i;s=i=0;
while(b[i])if(++i==n*m)return 1;
if(i/n<m-1){b[i]=b[i+n]=1;s+=f(n,m,b);b[i]=b[i+n]=0;}
if(i%n<n-1&&!(b[i]|b[i+1])){b[i]=b[i+1]=1;s+=f(n,m,b);b[i]=b[i+1]=0;}
return s;}
g(n,m){int b[99]={};return f(n,m,b);}

Для удобства чтения я включил этот ответ - все символы новой строки можно безопасно удалить до 230 байтов.

Определяет функцию, int g(int n, int m)которая возвращает количество элементов мозаичного изображения. Он использует вспомогательную функцию, fкоторая перебирает все допустимые фрагменты, помещая одно домино, возвращая его, а затем удаляя домино на общей доске.

Python 243

Я выбрал подход грубой силы:

• генерировать m * n / 2 направления;
• попробуйте поставить домино на доску m * n.

Если они все подходят и не осталось пробелов, у нас есть действительная запись.

Вот код:

import itertools as t
m,n=input()
c,u=0,m*n
for a in t.product([0,1],repeat=u/2):
 l,k,r,h=[' ',]*u,0,'-|',[1,m]
 for t in a:
  l[k]=r[t]
  k+=h[t]   
  if k%m<m and k/m<n and l[k]==' ':l[k]=r[t]
  k=''.join(l).find(' ',1)
 if k<0:c+=1
print c