Czy labirynt można rozwiązać?

20

Zagadka

  • Wydrukuj 0, jeśli nie można rozwiązać labiryntu n * m
  • Wydrukuj 1, jeśli labirynt n * m można rozwiązać (na 1 lub więcej sposobów)

(więc nie pytam o ścieżki, ale czy można to rozwiązać !!!)

Tablica wejściowa (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

Reguła Pozycja początkowa wynosi 0,0, a pozycja końcowa to n, m Możesz poruszać się tylko w poziomie i w pionie Najkrótszy kod wygrywa

dwana
źródło
Czy wejście powinno być ciągiem czy tablicą?
apsillers
3
Jeśli jest 1 (ściana) w (n, m), czy kod powinien zwrócić 0?
trichoplax
3
(To samo dla ściany o (0,0)?)
Martin Ender
3
Mówisz, że to labirynt × m, ale twoje indeksowanie sugeruje, że jest to labirynt (n + 1) × (m + 1).
Nick Matteo,
3
Nie mogę się doczekać rozwiązania regex =)
flawr

Odpowiedzi:

7

CJam, 42 41 39 36 35 bajtów

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

Na podstawie pomysłów zawartych w tej odpowiedzi .

4 bajty dzięki Optimizer.

Format wejściowy:

[[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
źródło
@Optimizer Dzięki za to. Ale potem znalazłem krótszą drogę ...
jimmy23013
1
q2Wts~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=- 36. Chociaż zakłada się, że pierwszymi trzema znakami wejściowymi będą[[0
Optimizer
7

Dyalog APL, 27 znaków

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

oceniane dane wejściowe. APL rozróżnia macierz od wektora wektorów. Ten program zakłada, że ​​wejście jest macierzą.

(~×⍳∘⍴)Ajest widelcem równoważnym (~A) × ⍳⍴A. Konieczne jest uniknięcie dwukrotnego wspominania lub wprowadzania zmiennej.

⍴Ama kształt A. Dla matrycy 4 na 7 kształt jest 4 7.

jest generatorem indeksu. ⍳4jest 1 2 3 4. ⍳4 7to wektory (1 1)(1 2)...(4 7)ułożone w matrycy 4 na 7.

~Aprzerzuca kawałki A.

×mnożąc ⍳⍴Aprzez odwrócone bity, zachowujemy współrzędne wszystkich wolnych komórek i zamieniamy wszystkie ściany w 0 0.

,niszczy macierz par współrzędnych, tj. linearyzuje ją do wektora. W takim przypadku wektor będzie składał się z par.

∘.-⍨Alub A∘.-Aodejmuje elementy Aparami. Zauważ, że tutaj elementy Asame w sobie są parami.

| całkowita wartość

+/¨zsumuj każdą parę wartości bezwzględnych. To daje nam odległości siatki między każdą parą komórek w labiryncie, z wyjątkiem ścian.

1≥interesują nas tylko sąsiedzi w odległości nie większej niż 1, nie obejmuje to również ścian. Teraz mamy macierz sąsiedztwa wykresu.

∨.∧⍨⍣≡ Floyd - algorytm przechwytywania przechwytywania Warshalla

(f⍣n)A(nieużywany tutaj), gdzie nliczba całkowita jest operatorem mocy. Ma ona zastosowanie fdo A nczasów: f f ... f A.

(f⍣g)Agdzie gjest funkcją, to operator punktu stałego, znany również jako „limit mocy”. Utrzymuje się na obliczaniu serii A, f A, f f A, ... aż ((f⍣i)A) g ((f⍣(i+1))A)Zwraca true dla niektórych i. W tym przypadku używamy match ( ) jako g.

∨.∧⍨Alub A∨.∧Ajest krokiem w algorytmie Floyda. f.gjest uogólnieniem mnożenia macierzy ( +.×), tutaj używamy koniunkcji ( ) i disjunction ( ) zamiast +i ×.

⊃⌽ Po ⍣≡wystarczającym zastosowaniu kroku i osiągnięciu stanu stabilnego musimy spojrzeć w prawy górny róg matrycy, aby uzyskać wynik, więc odwracamy go ( ) i bierzemy pierwszy, lewy górny element ( ).

Wizualizacja ⍣≡kroków

ngn
źródło
5

Python, 164 bajty

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

Nie chciałem tego publikować, ponieważ jest to praktycznie sposób, w jaki normalnie robię zalanie, tylko lekko golfa. Ale i tak jest.

Sp3000
źródło
4

Perl, 73 bajty

69 bajtów kodu + 4 bajty dla -n0E(nie jestem pewien, jak liczono tagi w 2014 roku, więc policzyłem je dla 4 zamiast 2, ale to nie ma większego znaczenia).

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

Wypróbuj online! (a jeśli zastąpi 1111011linię z 1111111, labirynt nie jest już rozwiązywalne, a wyjście będzie 0zamiast 1: Wypróbuj go online )

Objaśnienia:

Ten kod znajdzie każdą osiągalną komórkę labiryntu (i oznaczy je a A): jeśli komórka dotknie komórki oznaczonej przez A, jest osiągalna i oznaczymy ją Arównież; i robimy to ponownie ( redo). Dokonuje się tego dzięki dwóm wyrażeniom regularnym: s/(^0|A)(.{@{+}})?0/A$2A/ssprawdza, czy spacja znajduje się po prawej lub na dole a A, a s/0(.{@{+}})?A/A$1A/ssprawdza, czy spacja jest po lewej, czy na górze A. Na koniec, jeśli ostatnia komórka zawiera Aosiągalny, w przeciwnym razie nie (to say/A$/+0sprawdza; +0jest tutaj, aby upewnić się, że wynik będzie 0lub 1zamiast pustego ciągu i 1).
Pamiętaj, że /.*/dopasuje całą linię, a tym samym ustawienie@+do indeksu końca pierwszego wiersza, który okazuje się być rozmiarem linii, co pozwala na użycie, .{@{+}}aby dopasować dokładnie tyle znaków, ile jest na linii. ( @{+}jest równoważne @+, ale tylko pierwszy może być użyty w wyrażeniu regularnym)

Dada
źródło
W tym przypadku testowym kod uważa labirynt za rozwiązalny, nawet jeśli ostateczna pozycja to 1.
Jitse
@Jitse Dobry połów. W rzeczywistości było to spowodowane tym, że łącza TIO nie używały odpowiedniego kodu (wydaje mi się, że była to wcześniejsza wersja i nie zauważyłem go). Odpowiedź jest nadal aktualna i zaktualizowałem linki TIO. Twój przykład działa, a następnie dobrze: Wypróbuj online!
Dada
Och, racja! Dzięki za wyjaśnienie, podoba mi się to podejście.
Jitse
@ Jitse dzięki, to jeden z moich ulubionych golfów :)
Dada
3

Ruby, 133 130 129 znaków

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]

Wejście na STDIN, wyjściach 1lub 0na STDOUT.

Irytująco długo. Po prostu wykonuje wypełnienie 1s z (0, 0), a następnie sprawdza, czy kwadrat „końca” to 1.

Klamka
źródło
Czy to potraktuje labirynt jako rozwiązalny, jeśli zawiera on już 1 w (n, m)?
trichoplax
2

Java, 418 bajtów

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);}}}

Mój pierwszy golf golfowy. Nie wiem, dlaczego wybrałem Javę - to takie złe dla gry w golfa xD

Przykładowy labirynt zostanie wprowadzony przez stdin w następujący sposób:

......#;.....#.;....#..;#......
bace1000
źródło
1
Pro wskazówka: nazwij swoją klasę na coś o długości jednego znaku, porzuć spację między String[]i a, i weź dane wejściowe z argumentów wiersza poleceń zamiast StdIn, co jest dozwolone.
Pavel
1

Python 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))

Wydłużyło się to znacznie dłużej, niż się spodziewałem :( W każdym razie dodam wyjaśnienie, gdy nie będę mógł dłużej grać w golfa.

FryAmTheEggman
źródło
1

J, 75 znaków

Zasilanie macierzy sąsiedztwa (bardzo mało czasu i pamięci nieefektywne). (Czy nazywa się to powering po angielsku?)

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

Niektóre przypadki testowe:

   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
źródło
0

Python 3 , 184 bajty

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)]))

Wypróbuj online!

Matthew Jensen
źródło