Napisz program lub funkcję, która podając dodatnią wartość n i m oblicza liczbę prawidłowych odrębnych nachyleń domina, które można zmieścić w prostokącie n na m . Jest to sekwencja A099390 w Online Encyclopedia of Integer Sequences . Możesz przyjmować dane wejściowe w postaci argumentów funkcji, CLA lub standardowego wejścia, w dowolnym rozsądnym formacie. Musisz zwrócić lub wydrukować jedną liczbę całkowitą jako wynik.

Każde kafelkowanie nie może pozostawiać żadnych przerw, a każdy odrębny kafelek jest liczony, w tym obroty, odbicia itp. Na przykład, kafelki dla 2x3 to:

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

Przykładowe wejścia / wyjścia:

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

Twój program powinien teoretycznie działać dla każdego n i m , ale jeśli program wymaga zbyt dużo pamięci lub twój typ danych przelewa to usprawiedliwiona. Twój program musi jednak działać poprawnie dla dowolnego n, m <= 8.

Najkrótszy kod w bajtach wygrywa.

Pyth, 30 29 bajtów

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

Wypróbuj online: pakiet demonstracyjny / testowy

Wszystkie przykładowe dane wejściowe działają w kompilatorze online. Ostatni trwa jednak kilka sekund.

Wyjaśnienie:

W moim kodzie zdefiniuję funkcję rekurencyjną y. Funkcja ypobiera listę współrzędnych 2D i zwraca liczbę różnych nachyleń domina przy użyciu tych współrzędnych. Np. y([[0,0], [0,1]]) = 1(Jedno domino poziome), y([[0,0], [1,1]]) = 0(współrzędne nie sąsiadują) i y([[0,0], [0,1], [1,0], [1,1]]) = 2(dwa domino poziome lub dwa pionowe). Po zdefiniowaniu funkcji Zadzwonię go z wszystkich współrzędnych [x,y]z x in [0, 1, m-1], y in [0, 1, n-1].

Jak działa funkcja rekurencyjna? To całkiem proste. Jeśli lista współrzędnych jest pusta, istnieje dokładnie jeden poprawny kafelek i yzwraca 1.

W przeciwnym razie biorę pierwszą współrzędną z listy b[0]i szukam pozostałych współrzędnych w poszukiwaniu sąsiadów. Jeśli nie ma sąsiada b[0], to nie jest możliwe kafelkowanie, dlatego zwracam 0. Jeśli jest jeden lub więcej sąsiadów, liczba tilowań to (liczba tilings, w których łączę się b[0]z pierwszym sąsiadem za pośrednictwem domeny, plus liczba przechyleń, w których łączę się b[0]z drugim sąsiadem, plus ...) Więc wywołuję funkcję rekurencyjnie dla każdego sąsiada ze skróconą listą (poprzez usunięcie dwóch współrzędnych b[0]i sąsiada). Następnie sumuję wszystkie wyniki i zwracam je.

Ze względu na kolejność strun możliwe są zawsze tylko dwa sąsiedzi, ten po prawej stronie i ten poniżej. Ale mój algorytm się tym nie przejmuje.

                          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  

Matlab, 292

Jestem pewien, że można to znacznie skrócić, przenosząc go na inny język.

Podstawową ideą jest brutalne: wymyśliłem rodzaj wyliczenia wszystkich sposobów umieszczania m*n/2cegieł domina na m*nplanszy. Ale to wyliczenie obejmuje również wiele nieprawidłowych przechyłów (cegieł, które nakładają się lub wychodzą poza planszę). Program konstruuje wszystkie przechyłki i liczy tylko te prawidłowe. Chodzi o złożoność środowiska wykonawczego O(2^(m*n/2) * m*n). Pamięć nie stanowi problemu, 8x8ponieważ potrzebuje tylko O(m*n)pamięci. Ale potrzebny czas 8x8to około 20 dni.

Oto w pełni skomentowana wersja, która wyjaśnia, co się dzieje.

PS: Jeśli ktoś wie, jak sprawić, by wyróżnianie składni Matlaba działało, prosimy o dołączenie odpowiedniego znacznika w tej odpowiedzi!

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

Oto w pełni golfowy:

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 bajtów

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);}

Dla czytelności odłożyłem ręcznie tę odpowiedź - wszystkie znaki nowej linii można bezpiecznie usunąć, aby dostać się do 230 bajtów.

Definiuje funkcję int g(int n, int m)zwracającą liczbę przechyleń. Wykorzystuje funkcję pomocniczą, fktóra iteruje wszystkie prawidłowe przechylenia, umieszczając jedno domino, rekursywnie, a następnie usuwając domino ze wspólnej tablicy.

Python 243

Zdecydowałem się na brutalne podejście:

• generować m * n / 2 kierunków;
• spróbuj dopasować domino na planszy m * n.

Jeśli wszystkie pasują i nie ma już wolnych miejsc, mamy prawidłowy wpis.

Oto kod:

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