Biorąc pod uwagę labirynt na stdin i punkt wejścia, napisz program, który drukuje ścieżkę do wyjścia na stdout. Każda ścieżka jest akceptowalna, o ile twój program nie generuje trywialnej ścieżki (przechodzącej przez każdy punkt w labiryncie) dla każdego labiryntu.
Na wejściu ściany są oznaczone a, #
a punkt wejścia a @
. Możesz użyć dowolnych znaków, aby narysować labirynt i ścieżkę na wyjściu, o ile wszystkie są różne.
Możesz założyć, że:
- Punkty wejścia i wyjścia znajdują się na krawędziach wejścia
- Każdy wiersz wejścia ma tę samą długość
- Labirynt jest rozwiązywalny i nie ma cykli
- Jest tylko jeden punkt wyjścia
Najkrótsze rozwiązanie według liczby znaków (Unicode) wygrywa.
Przykłady
(zauważ, że wejścia są wypełnione spacjami)
####
# #
@ #####
# #
#
#######
####
# #
@*#####
#* #
#******
#######
### ###################
### # #
## ######### # #
# ##### #
############### #@##
###*###################
###*********#*********#
## *#########* # *#
# *********** #####**#
############### #@##
code-golf
path-finding
maze
Lowjacker
źródło
źródło
Odpowiedzi:
Ruby 1.9, 244 znaki
Dane wyjściowe dla dwóch przykładów:
Edycje:
źródło
ANSI C (
384373368 znaków)Oto moja próba C. Skompilowano i uruchomiono w systemie Mac OS X.
Przykładowe dane wyjściowe dla kilku testów:
Ograniczenia: Działa tylko dla labiryntów do 1000 znaków, ale można to łatwo zwiększyć. Właśnie wybrałem dowolny numer zamiast zawracać sobie głowę malloc / remalloc.
Jest to także najbardziej obciążony kod, jaki kiedykolwiek napisałem. 19 ostrzeżeń, choć wygląda to jeszcze bardziej z podświetleniem kodu XCode. :RE
EDYCJE: Edytowane i testowane, aby upuścić int z main, aby użyć ~ zamiast! = EOF i putchar zamiast printf. Dzięki za komentarze!
źródło
int
” przedmain
i zapisz 4 znaki. Użyj równieżputchar(*(s-1))
zamiast,printf("%c",*(s-1))
aby zapisać 4 kolejne.0xA
przez10
i!=
przez^
.~
operatora, aby sprawdzić EOF:while(~(c=getchar())
Python, 339 znaków
Generuje najkrótszą ścieżkę przez labirynt.
Dane wyjściowe na przykład labirynty:
źródło
Python -
510421 znakówźródło
*
w prawym dolnym rogu, w pierwszym przypadku testowym (python 2.6.1). jakieś pomysły?print b,r
i teprint (i,j)
, które, jak przypuszczam, służyły do debugowania :)Python 3 , 275 bajtów
Wypróbuj online!
Port mojej odpowiedzi, aby znaleźć najkrótszą trasę na drodze ASCII .
Używa
'#'
początku,'*'
końca,'@'
ściany i' '
pustej przestrzeni. W tym przypadku funkcjaq
jest funkcją pomocniczą, która zwraca jednowymiarową tablicę z najkrótszą ścieżką w labiryncie. Funkcjęf
można skrócić o 4 bajty, nie przypisując zmiennejs
. Jest to niezwykle nieefektywne i prawdopodobnie przekroczy limit czasu, ponieważ wywołuje funkcję wyszukiwania ścieżki dla każdej postaci w labiryncie.źródło