Количество действительных лабиринтов

12

Учитывая WxHсетку, сколько возможных лабиринтов есть?

Что вы знаете о лабиринте:

  1. Сетка ровно Hквадратная и Wквадратная.
  2. Существует три типа квадратов: Start, Finish и Empty. Ваш лабиринт должен содержать ровно 1 начало и 1 конец, а все оставшиеся квадраты пусты.
  3. Есть стены, окружающие весь лабиринт.
  4. Стены могут существовать на границе между любыми двумя квадратами, если это не нарушает нижеследующее правило:
  5. Должен существовать путь от стартового квадрата до финишного квадрата.

Поэтому, учитывая два числа, Wи Hвы должны возвращать единственное число , представляющее собой количество возможных конфигураций площади / стена. Вам гарантировано, чтоW*H > 1

Например, 2x2лабиринт имеет совершенно 100разные возможные конфигурации.

Это код-гольф, поэтому выигрывает самый короткий ответ!

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 Натан Меррилл
источник
Есть ли ограничения по размеру и / или времени выполнения? Если кто-то не найдет алгоритм, который может эффективно рассчитать количество (что выглядит жестко), я ожидаю, что большинство решений будет иметь экспоненциальное время выполнения. Это означает, что они взорвутся даже при умеренных размерах.
Рето Коради
@RetoKoradi нет, никаких ограничений времени выполнения. Я не уверен, что ограничения сделают проблему невозможной или нет.
Натан Меррилл

Ответы:

3

Python 2, 329 310 байт

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

Это версия программы для гольфа (и гораздо более неэффективная), которую я использовал при обсуждении проблемы с @Nathan. Я могу сохранить несколько байтов, заменив некоторые отступы пробелами, но я сохраню это позже.

Алгоритм просто генерирует каждый лабиринт, а затем заливает заливку с самого начала, проверяя, пройдем ли мы финиш в какой-то момент или нет.

Sp3000
источник