Liczba prawidłowych labiryntów

12

Biorąc pod uwagę WxHsiatkę, ile jest możliwych labiryntów?

Rzeczy, które wiesz o labiryncie:

  1. Siatka ma dokładnie Hkwadraty wysokie i Wszerokie kwadraty.
  2. Istnieją trzy rodzaje kwadratów: Start, Zakończ i Pusty. Twój labirynt musi zawierać dokładnie 1 początek i 1 koniec, a wszystkie pozostałe kwadraty są puste.
  3. Mury otaczają cały labirynt.
  4. Ściany mogą istnieć na krawędzi między dowolnymi dwoma kwadratami, chyba że złamie to poniższą zasadę:
  5. Musi istnieć ścieżka od kwadratu początkowego do kwadratu końcowego.

Dlatego, biorąc pod uwagę dwie liczby, Wi Hmusisz zwrócić pojedynczy numer reprezentujący liczbę możliwych konfiguracji kwadratu / ściany. Masz gwarancję, żeW*H > 1

Na przykład 2x2labirynt ma dokładnie 100różne możliwe konfiguracje.

To jest golf golfowy, więc wygrywa najkrótsza odpowiedź!

code-golf maze code-golf string whitespace code-golf arithmetic code-golf pyth code-golf game code-golf string code-challenge code-challenge ascii-art compression king-of-the-hill c c++ java code-challenge math optimization code-challenge math code-golf kolmogorov-complexity code-golf string Nathan Merrill
źródło
Czy są jakieś ograniczenia dotyczące rozmiaru i / lub środowiska wykonawczego? O ile ktoś nie znajdzie algorytmu, który może efektywnie obliczyć liczbę (która wygląda na trudną), spodziewam się, że większość rozwiązań będzie miała wykładniczy czas działania. Oznacza to, że będą implodować nawet w umiarkowanych rozmiarach.
Reto Koradi,
@RetoKoradi nie, bez ograniczeń w czasie wykonywania. Nie jestem pewien, czy ograniczenia uniemożliwiłyby problem, czy nie.
Nathan Merrill,

Odpowiedzi:

3

Python 2, 329 310 bajtów

from itertools import*
w,h=input()
R=range(w*h)
p=product
n=0
Z=[(x,y)for x,y in p(R,R)if abs(x%w-y%w)+abs(x/w-y/w)<2]
for s,f,W in p(R,R,p(*[((),z)for z in Z if z[0]<z[1]])):
 V={s};C=[s];v=0
 while C:
  c=C.pop();v|=c==f!=s;V|={c}
  for o,q in Z:C+=(c==o)*len({q,(o,q),(q,o)}-(V|set(W)))/3*[q] 
 n+=v
print n

Jest to gra w golfa (i znacznie bardziej nieefektywna) programu, którego używałem podczas omawiania problemu z @Nathan. Mogę zapisać kilka bajtów, zastępując niektóre wcięcia spacjami tabulatorami, ale zachowam to na później.

Algorytm generuje po prostu każdy labirynt, a następnie wypełnia go od samego początku, sprawdzając, czy miniemy metę w pewnym momencie, czy nie.

Sp3000
źródło