Żółw chce poruszać się wzdłuż siatki, aby dostać się do jedzenia. Chce wiedzieć, ile ruchów zajmie mu dotarcie.
Ponieważ jest wolny, teleportery ustawiają się wokół jego domeny, z której będzie korzystać, jeśli skróci to jego ścieżkę. Lub unikaj ich, jeśli wydłuży to jego drogę.
Poznaj żółwia
🐢
Żółw żyje na siatce
Żółw nie może jednak przejść na plac z górą
Żółw chce zjeść swoją truskawkę i chce wiedzieć, ile czasu zajmie dojście do jego truskawek
Wyzwanie
Biorąc pod uwagę początkową konfigurację wyjściową siatki, liczbę ruchów zajmie żółwia, aby osiągnąć swoją truskawkę.
Zasady
Możesz założyć, że siatka wejściowa ma rozwiązanie
Każda siatka będzie miała tylko jeden,
strawberry
dwaportals
i jedenturtle
Siatkę wejściową można wprowadzić w dowolnym dogodnym formacie
Powinieneś traktować
teleporters
przedmioty jednorazowego użytkuTurn, w którym żółw porusza się na pole
teleporter
, jest już na odpowiednimteleporter
. Nigdy nie przechodzi nateleporter
i pozostaje tam, aby wykonać ruchNajkrótsza ścieżka nie musi korzystać z portalu
Żółw nie może przejść do górskich kafelków
Można użyć dowolnego znaku ASCII lub całkowitą do reprezentacji
mountains
,turtle
,empty grid square
,strawberry
Możesz użyć tego samego znaku lub dwóch różnych znaków ASCII lub liczb całkowitych do przedstawienia
teleporter
parSiatka może mieć więcej niż jedną ścieżkę o tej samej najkrótszej długości
To jest golf golfowy
Wyjaśnienia zasad
- Powinieneś traktować
teleporters
przedmioty jednorazowego użytku.
Można to rozwiązać tylko dwukrotnie wchodząc i wychodząc z portali. W momencie dokonywania tego wyjaśnienia oba rozwiązania działały, zakładając, że były albo jednorazowego użytku, albo nie było powodu, aby wypróbować wcześniej używane kwadraty. Aby uniknąć zerwania z ciężko wypracowanymi rozwiązaniami, wydawało się to najlepszym sposobem na uwzględnienie tego ustawienia. Dlatego byłoby to uważane za nieprawidłową siatkę.
Przypadki testowe sformatowane jako listy
[ ['T', 'X', 'X', 'S', 'X'], ['X', 'X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'] ] --> 3
[ ['T', 'M', 'X', 'S', 'X'], ['X', 'M', 'X', 'X', 'X'], ['O', 'X', 'X', 'X', 'O'] ] --> 4
[ ['T', 'M', 'X', 'S', 'O'], ['O', 'M', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'] ] --> 2
[ ['T', 'M', 'X', 'S', 'X'], ['O', 'M', 'X', 'X', 'X'], ['O', 'X', 'X', 'X', 'X'] ] --> 4
[ ['T', 'M', 'S', 'X', 'O'], ['X', 'M', 'M', 'M', 'M'], ['X', 'X', 'X', 'X', 'O'] ] --> 7
[ ['T', 'X', 'X', 'S', 'X'], ['O', 'M', 'M', 'M', 'X'], ['X', 'X', 'O', 'X', 'X'] ] --> 3
Przypadki testowe sformatowane dla ludzi
T X X S X
X X X X X
X X X X X --> 3
T M X S X
X M X X X
O X X X O --> 4
T M X S O
O M X X X
X X X X X --> 2
T M X S X
O M X X X
O X X X X --> 4
T M S X O
X M M M M
X X X X O --> 7
T X X S X
O M M M X
X X O X X --> 3
Kredyty
Projekt i struktura: Głodna mysz Arnauld
Proponowane wyzwania Edytuj porady: Kamil-drakari , beefster
źródło
Odpowiedzi:
JavaScript (ES7),
140 139138 bajtówPobiera dane wejściowe jako macierz liczb całkowitych z następującym odwzorowaniem:
Wypróbuj online!
W jaki sposób?
Główna funkcja wyszukiwania rekurencyjnegosol jest w stanie wyszukać konkretny kafelek t na planszy (jeśli jest wywoływane z t ≠ 0 ) lub dla dowolnego kafelka pod adresem ( x , y) do którego można dotrzeć z bieżącej pozycji ( X, Y) .
Śledzi długość bieżącej ścieżki wja i aktualizuje najlepszy wynik R do min ( R , i ) ilekroć żółw znajdzie truskawkę.
Najpierw jest wywoływany zt = 2 znaleźć pozycję początkową żółwia.
To się nazywat = - 1 po osiągnięciu portalu, aby żółw został teleportowany do innego portalu. Nie zwiększamyja podczas takiej iteracji.
Każda odwiedzana płytka jest tymczasowo ustawiona na górę, aby żółw nie poruszał się dwukrotnie po tej samej płytce na tej samej ścieżce. Jeśli zostaniemy uwięzieni w ślepym zaułku, rekursja po prostu zatrzymuje się bez aktualizacjiR .
Skomentował
źródło
Python 2 ,
441431341 bajtówWypróbuj online!
Wprowadź jako listy, ale używając liczb zamiast znaków (dzięki Quintec) i osobnej wartości dla miejsca docelowego teleportera. Te duże wcięcia powinny być znakami tabulacji, jeśli Stack Exchange je usunie. Wszelkie wskazówki lub pomysły szczególnie mile widziane, ponieważ czuję, że to może dostać
znacznienieco krótszy.Tabela znaków używanych w wyzwaniu do liczb używanych w moim programie znajduje się poniżej, ale możesz także użyć tego programu .
-10 bajtów dzięki Quintec, zmieniając dane wejściowe z używania znaków na liczby.
- Dużo bajtów dzięki Jonathanowi Frechowi, ElPedro i Jonathanowi Allanowi.
źródło
Python 2 , 391
397403422bajtówWypróbuj online!
Problem jest tłumaczony na wykres, a rozwiązaniem jest znalezienie najkrótszej ścieżki od żółwia do truskawki.
źródło