Можно ли решить лабиринт?

20

Головоломка

  • Выведите 0, если лабиринт не может быть решен
  • Выведите 1, если можно найти лабиринт n * m (одним или несколькими способами)

(поэтому я не спрашиваю пути, но если это возможно решить !!!)

Входной массив (2d):

[[0,0,0,0,0,0,1],[0,0,0,0,0,1,0],[0,0,0,0,1,0,0],[1,0,0,0,0,0,0]]

XXXXXXXXX
XS     XX
X     X X
X    X  X
XX     FX
XXXXXXXXX

0 = can pass through
1 = can not pass trough
[0][n] is the last block of the first line
[m][0] is the first block of the last line

Правило Начальная позиция - 0,0, а конечная позиция - n, m. Вы можете перемещаться только по горизонтали и вертикали. Самый короткий код выигрывает

dwana
источник
Должен ли ввод быть строкой или массивом?
Апсиллеры
3
Если в (n, m) есть 1 (стена), должен ли код возвращать 0?
трихоплакс
3
(То же самое для стены в (0,0)?)
Мартин Эндер
3
Вы говорите, что это лабиринт × m, но ваша индексация подразумевает, что это лабиринт (n + 1) × (m + 1).
Ник Маттео
3
Я с нетерпением жду решения регулярных выражений =)
flawr

Ответы:

7

CJam, 42 41 39 36 35 байт

Wq3>~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=

Основано на идеях в этом ответе .

4 байта благодаря Оптимизатору.

Формат ввода:

[[0 0 0 0 0 0 1] [0 0 0 0 0 1 0] [0 0 0 0 1 0 0] [1 0 0 0 0 0 0]]
jimmy23013
источник
@Optimizer Спасибо за это. Но потом я нашел более короткий путь ...
jimmy23013
1
q2Wts~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=- 36. Хотя предполагается, что первые три символа ввода будут[[0
Оптимизатор
7

Дьялог АПЛ, 27 знаков

⊃⌽∨.∧⍨⍣≡1≥+/¨|∘.-⍨,(~×⍳∘⍴)⎕

оценил вклад. APL различает матрицу и вектор векторов. Эта программа предполагает, что ввод является матрицей.

(~×⍳∘⍴)Aявляется вилкой, эквивалентной (~A) × ⍳⍴A. Необходимо избегать упоминания дважды или введения переменной.

⍴Aэто форма A. Для матрицы 4 на 7 форма имеет вид 4 7.

это генератор индекса. ⍳4есть 1 2 3 4. ⍳4 7векторы, (1 1)(1 2)...(4 7)расположенные в матрице 4 на 7.

~Aпереворачивает биты A.

×умножая ⍳⍴Aна перевернутые биты, мы сохраняем координаты всех свободных ячеек и превращаем все стены в 0 0.

,распределяет матрицу координатных пар, т.е. линеаризует ее в вектор. В этом случае вектор будет состоять из пар.

∘.-⍨Aили A∘.-Aвычитает элементы Aпопарно. Обратите внимание, что здесь элементы Aсами являются парами.

| абсолютная величина

+/¨Суммируйте каждую пару абсолютных значений. Это дает нам сетку расстояний между каждой парой клеток в лабиринте, за исключением стен.

1≥нас интересуют только соседи на расстоянии не более 1, это тоже исключает стены. Теперь у нас есть матрица смежности графа.

∨.∧⍨⍣≡ Флойд - алгоритм транзитивного замыкания Варшалла

(f⍣n)A(здесь не используется) где nцелое число - оператор степени. Это относится fк A nвремени: f f ... f A.

(f⍣g)Aгде g- функция, оператор с фиксированной запятой, он же «предел мощности». Он продолжает вычисления серии A, f A, f f A, ... до ((f⍣i)A) g ((f⍣(i+1))A)возвращения верно для некоторых i. В этом случае мы используем match ( ) как g.

∨.∧⍨Aили A∨.∧Aэто шаг в алгоритме Флойда. f.gявляется обобщением матричного умножения ( +.×), здесь мы используем conunction ( ) и disjunction ( ) вместо +и ×.

⊃⌽ После того ⍣≡, как шаг был применен достаточно раз и достиг стабильного состояния, мы должны посмотреть в верхнем правом углу матрицы, чтобы получить результат, поэтому мы переворачиваем его ( ) и берем первый, левый верхний элемент ( ).

Визуализация ⍣≡шагов

СПП
источник
5

Python, 164 байта

def s(a):
 d=[(0,0)]
 while d:i,j=d.pop();a[i][j]=2;d+=[(x,y)for x,y in[(i-1,j),(i,j-1),(i+1,j),(i,j+1)]if len(a[0])>y>-1<x<len(a)and a[x][y]<1]
 return a[-1][-1]>1

Я неохотно писал об этом, потому что это практически то, как я обычно делаю заливку, просто слегка играю в гольф. Но здесь это все равно.

Sp3000
источник
4

Perl, 73 байта

69 байт кода + 4 байта для -n0E(не знаю, как подсчитывались теги в 2014 году, поэтому я посчитал их 4 вместо 2, но это не имеет большого значения).

/.*/;s/(^0|A)(.{@{+}})?0/A$2A/s||s/0(.{@{+}})?A/A$1A/s?redo:say/A$/+0

Попробуйте онлайн! (и если вы замените 1111011строку на 1111111, лабиринт больше не будет разрешен, и результат будет 0вместо 1: Попробуйте онлайн! )

Пояснения:

Этот код найдет каждую достижимую ячейку лабиринта (и пометит их с помощью a A): если ячейка касается ячейки, помеченной символом a A, она достижима, и мы помечаем ее Aтоже; и мы делаем это снова ( redo). Это делается благодаря двум регулярным выражениям: s/(^0|A)(.{@{+}})?0/A$2A/sпроверяет, находится ли пробел справа или снизу A, а s/0(.{@{+}})?A/A$1A/sпроверяет, находится ли пробел слева или сверху а A. В конце, если в последней ячейке есть Aдостижимость, в противном случае это не так (это то, что say/A$/+0проверяет; +0здесь, чтобы убедиться, что результат будет 0или 1вместо пустой строки и 1).
Обратите внимание, что /.*/будет соответствовать всей строке, таким образом, настройка@+до индекса конца первой строки, который соответствует размеру строки, который позволяет использовать .{@{+}}для соответствия ровно столько символов, сколько имеется в строке. ( @{+}эквивалентно @+, но только первое может использоваться в регулярных выражениях)

папа
источник
Для этого теста ваш код считает, что лабиринт разрешим, даже если конечная позиция 1.
Джитс
@ Джитс Хорошо, лови. На самом деле, это было потому, что ссылки TIO не использовали правильный код (я думаю, это была какая-то более ранняя версия, и я ее не заметил). Ответ остается в силе, и я обновил ссылки TIO. Ваш пример работает хорошо: попробуйте онлайн!
Дада
О верно! Спасибо за разъяснения, мне нравится этот подход.
Джитсе
@ Jitse спасибо, это один из моих любимых гольфов :)
Дада
3

Рубин, 133 130 129 знаков

a=eval gets
f=->x,y{a[x][y]=1
[[-1,0],[1,0],[0,-1],[0,1]].map{|o|d,e=x+o[0],y+o[1]
f[d,e]if a[d]&&a[d][e]==0}}
f[0,0]
p a[-1][-1]

Вход на STDIN, выходы 1или 0на STDOUT.

Досадно долго. Он просто выполняет заливку 1s из from (0, 0), а затем проверяет, является ли «конечный» квадрат a 1.

Дверная ручка
источник
Будет ли это рассматривать лабиринт как разрешимый, если он уже содержит 1 в (п, м)?
Трихоплакс
2

Java, 418 байт

import java.util.Scanner;public class Solvable{static int w,h;public static void main(String[] a){String[]i=new Scanner(System.in).nextLine().split(";");h=i.length+2;w=i[0].length()+2;int[]m=new int[w * h];for(int x=1;x<w-1;x++)for(int y=1;y<h-1;y++)m[y*w+x]=i[y-1].charAt(x-1)<'.'?0:1;f(m,w+1);System.out.println(m[w*h-w-2]>0?0:1);}static void f(int[]m,int i){if(m[i]>0){m[i]--;f(m,i-1);f(m,i+1);f(m,i-w);f(m,i+w);}}}

Мой первый код гольф. Я не знаю, почему я выбрал Java - это так плохо для игры в гольф xD

Пример лабиринта будет введен через stdin следующим образом:

......#;.....#.;....#..;#......
bace1000
источник
1
Совет от профессионала: назовите свой класс длиной в один символ, пропустите пробел между String[]и aи получите ввод из аргументов командной строки, а не из StdIn, что разрешено.
Павел
1

Питон 184 188

def f(a,x=0,y=0,h=[]):s=h+[[x,y]];X,Y=len(a[0]),len(a);return([x,y]in h)==(x>=X)==(y>=Y)==(x<0)==(y<0)==a[y][x]<(x==X-1and y==Y-1or f(a,x-1,y,s)|f(a,x+1,y,s)|f(a,x,y-1,s)|f(a,x,y+1,s))

Это заняло гораздо больше времени, чем я думал :( В любом случае, я добавлю объяснение, как только я больше не смогу играть в гольф.

FryAmTheEggman
источник
1

J, 75 символов

Включение матрицы смежности (очень мало времени и памяти). (Это называется powering на английском языке?)

   ({.@{:@(+./ .*.^:_~)@(+:/~@,*2>(>@[+/@:|@:->@])"0/~@,@(i.@#<@,"0/i.@#@|:)))

Некоторые тестовые случаи:

   m1=. 0 0 0 0 0 0 1,. 0 0 0 0 0 1 0,.  0 0 0 0 1 0 0,. 1 0 0 0 0 0 0
   m2=. 0 1 1 ,. 0 0 0
   m3=. 0 1 0 ,. 1 1 0
   m4=. 0 1 1 0 ,. 0 0 1 0
   ({.@{:@(+./ .*.^:_~)@(+:/~@,*2>(>@[+/@:|@:->@])"0/~@,@(i.@#<@,"0/i.@#@|:))) every m1;m2;m3;m4
1 1 0 0
randomra
источник
0

Python 3 , 184 байта

f=lambda m,x=0,y=0,n=0:n<len(m)*len(m[0])and m[x][y]<1and((x,y)==(len(m)-1,len(m[0])-1)or any(0<=i<len(m)and 0<=j<len(m[0])and f(m,i,j,n+1)for i,j in[(x-1,y),(x,y-1),(x+1,y),(x,y+1)]))

Попробуйте онлайн!

Мэтью Дженсен
источник