Número de labirintos válidos

12

Dada uma WxHgrade, quantos labirintos possíveis existem?

Coisas que você sabe sobre o labirinto:

  1. A grade é exatamente Hquadrados altos e Wquadrados largos.
  2. Existem três tipos de quadrados: Iniciar, Finalizar e Vazio. Seu labirinto deve conter exatamente 1 Start e 1 Finish, e todos os quadrados restantes estão vazios.
  3. Há paredes ao redor do labirinto inteiro.
  4. Podem existir paredes na borda entre dois quadrados, a menos que quebre a regra abaixo:
  5. Deve haver um caminho do quadrado Iniciar até o quadrado Concluir.

Portanto, com dois números We H, você deve retornar um único número que representa o número possível de configurações de quadrado / parede. Você está garantido queW*H > 1

Por exemplo, o 2x2labirinto tem 100configurações possíveis exatamente diferentes.

Este é um código-golfe, então a resposta mais curta vence!

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
fonte
Existem restrições quanto ao tamanho e / ou tempo de execução? A menos que alguém encontre um algoritmo que possa calcular a contagem com eficiência (o que parece difícil), espero que a maioria das soluções tenha tempo de execução exponencial. O que significa que eles implodirão em tamanhos moderados.
Reto Koradi 16/07/2015
@RetoKoradi não, sem restrições de tempo de execução. Não tenho certeza se as restrições tornariam o problema impossível ou não.
Nathan Merrill

Respostas:

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 é a versão golfada (e muito mais ineficiente) do programa que eu estava usando enquanto discutia o problema com o @Nathan. Posso salvar alguns bytes substituindo alguns recuos de espaço por guias, mas guardarei isso para mais tarde.

O algoritmo é simplesmente gerar todos os labirintos e, em seguida, inundar o preenchimento desde o início, vendo se passamos o acabamento em algum momento ou não.

Sp3000
fonte