Jumlah labirin yang valid

12

Diberi WxHkotak, berapa banyak labirin yang mungkin ada?

Hal-hal yang Anda ketahui tentang labirin:

  1. Kotak persis Hkotak tinggi dan Wkotak lebar.
  2. Ada tiga jenis kotak: Mulai, Selesai, dan Kosong. Labirin Anda harus berisi tepat 1 Mulai dan 1 Selesai, dan semua kotak yang tersisa kosong.
  3. Ada dinding yang mengelilingi seluruh labirin.
  4. Dinding dapat ada di tepi antara dua kotak, kecuali jika melanggar aturan di bawah ini:
  5. Harus ada jalur dari kotak Mulai ke kotak Selesai.

Oleh karena itu, diberikan dua angka, Wdan H, Anda harus mengembalikan satu angka yang mewakili jumlah kemungkinan konfigurasi persegi / dinding. Anda dijamin akan melakukannyaW*H > 1

Misalnya, 2x2labirin memiliki 100konfigurasi yang mungkin sangat berbeda.

Ini adalah kode-golf sehingga jawaban terpendek menang!

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
sumber
Apakah ada batasan ukuran dan / atau runtime? Kecuali seseorang menemukan algoritma yang dapat menghitung hitungan secara efisien (yang terlihat sulit), saya berharap sebagian besar solusi akan mengalami runtime eksponensial. Artinya, mereka akan meledak bahkan pada ukuran sedang.
Reto Koradi
@RetoKoradi tidak, tidak ada kendala runtime. Saya tidak yakin apakah kendala akan membuat masalah menjadi tidak mungkin atau tidak.
Nathan Merrill

Jawaban:

3

Python 2, 329 310 byte

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

Ini adalah versi golf (dan jauh lebih tidak efisien) dari program yang saya gunakan saat membahas masalah dengan @Nathan. Saya dapat menyimpan beberapa byte dengan mengganti beberapa inden ruang dengan tab, tetapi saya akan menyimpannya untuk nanti.

Algoritma ini hanya menghasilkan setiap labirin, lalu mengisi banjir dari awal, melihat apakah kita melewati finish di beberapa titik atau tidak.

Sp3000
sumber