Número de laberintos válidos

12

Dada una WxHcuadrícula, ¿cuántos laberintos posibles hay?

Cosas que sabes sobre el laberinto:

  1. La cuadrícula es exactamente Hcuadrados altos y Wcuadrados anchos.
  2. Hay tres tipos de cuadrados: Inicio, Fin y Vacío. Tu laberinto debe contener exactamente 1 inicio y 1 final, y todos los cuadrados restantes están vacíos.
  3. Hay paredes que rodean todo el laberinto.
  4. Pueden existir muros en el borde entre dos cuadrados, a menos que rompa la siguiente regla:
  5. Debe existir un camino desde el cuadro de Inicio hasta el cuadro de Fin.

Por lo tanto, dados dos números Wy Hdebe devolver un solo número que represente el número de posibles configuraciones de cuadrado / pared. Tienes garantizado queW*H > 1

Por ejemplo, el 2x2laberinto tiene exactamente 100diferentes configuraciones posibles.

Este es un código de golf, por lo que gana la respuesta más corta.

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
fuente
¿Hay alguna restricción en el tamaño y / o tiempo de ejecución? A menos que alguien encuentre un algoritmo que pueda calcular el recuento de manera eficiente (lo que parece difícil), espero que la mayoría de las soluciones tengan un tiempo de ejecución exponencial. Lo que significa que implosionarán incluso en tamaños moderados.
Reto Koradi
@RetoKoradi no, no hay restricciones de tiempo de ejecución. No estoy seguro de si las restricciones harían el problema imposible o no.
Nathan Merrill

Respuestas:

3

Python 2, 329 310 bytes

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

Esta es la versión de golf (y mucho más ineficiente) del programa que estaba usando mientras discutía el problema con @Nathan. Puedo guardar algunos bytes reemplazando algunas sangrías de espacio con pestañas, pero lo guardaré para más adelante.

El algoritmo es simplemente generar cada laberinto, luego inundar el relleno desde el principio, ver si pasamos el final en algún momento o no.

Sp3000
fuente