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
Odpowiedzi:
CJam,
4241393635 bajtówNa podstawie pomysłów zawartych w tej odpowiedzi .
4 bajty dzięki Optimizer.
Format wejściowy:
źródło
q2Wts~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=
- 36. Chociaż zakłada się, że pierwszymi trzema znakami wejściowymi będą[[0
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ą.(~×⍳∘⍴)A
jest widelcem równoważnym(~A) × ⍳⍴A
. Konieczne jest uniknięcie⎕
dwukrotnego wspominania lub wprowadzania zmiennej.⍴A
ma kształtA
. Dla matrycy 4 na 7 kształt jest4 7
.⍳
jest generatorem indeksu.⍳4
jest1 2 3 4
.⍳4 7
to wektory(1 1)(1 2)...(4 7)
ułożone w matrycy 4 na 7.~A
przerzuca kawałkiA
.×
mnożąc⍳⍴A
przez odwrócone bity, zachowujemy współrzędne wszystkich wolnych komórek i zamieniamy wszystkie ściany w0 0
.,
niszczy macierz par współrzędnych, tj. linearyzuje ją do wektora. W takim przypadku wektor będzie składał się z par.∘.-⍨A
lubA∘.-A
odejmuje elementyA
parami. Zauważ, że tutaj elementyA
same 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), gdzien
liczba całkowita jest operatorem mocy. Ma ona zastosowanief
doA
n
czasów:f f ... f A
.(f⍣g)A
gdzieg
jest funkcją, to operator punktu stałego, znany również jako „limit mocy”. Utrzymuje się na obliczaniu seriiA
,f A
,f f A
, ... aż((f⍣i)A) g ((f⍣(i+1))A)
Zwraca true dla niektórychi
. W tym przypadku używamy match (≡
) jakog
.∨.∧⍨A
lubA∨.∧A
jest krokiem w algorytmie Floyda.f.g
jest 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źródło
Python, 164 bajty
Nie chciałem tego publikować, ponieważ jest to praktycznie sposób, w jaki normalnie robię zalanie, tylko lekko golfa. Ale i tak jest.
źródło
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).Wypróbuj online! (a jeśli zastąpi
1111011
linię z1111111
, labirynt nie jest już rozwiązywalne, a wyjście będzie0
zamiast1
: 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 przezA
, jest osiągalna i oznaczymy jąA
również; i robimy to ponownie (redo
). Dokonuje się tego dzięki dwóm wyrażeniom regularnym:s/(^0|A)(.{@{+}})?0/A$2A/s
sprawdza, czy spacja znajduje się po prawej lub na dole aA
, as/0(.{@{+}})?A/A$1A/s
sprawdza, czy spacja jest po lewej, czy na górzeA
. Na koniec, jeśli ostatnia komórka zawieraA
osiągalny, w przeciwnym razie nie (tosay/A$/+0
sprawdza;+0
jest tutaj, aby upewnić się, że wynik będzie0
lub1
zamiast pustego ciągu i1
).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)źródło
1
.Ruby,
133130129 znakówWejście na STDIN, wyjściach
1
lub0
na STDOUT.Irytująco długo. Po prostu wykonuje wypełnienie
1
s z(0, 0)
, a następnie sprawdza, czy kwadrat „końca” to1
.źródło
Java, 418 bajtó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:
źródło
String[]
ia
, i weź dane wejściowe z argumentów wiersza poleceń zamiast StdIn, co jest dozwolone.Python 184
188Wydł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.
źródło
J, 75 znaków
Zasilanie macierzy sąsiedztwa (bardzo mało czasu i pamięci nieefektywne). (Czy nazywa się to powering po angielsku?)
Niektóre przypadki testowe:
źródło
Python 3 , 147 bajtów
Wypróbuj online!
Port mojej odpowiedzi, aby znaleźć najkrótszą trasę na drodze ASCII .
źródło
Python 3 , 184 bajty
Wypróbuj online!
źródło