Jesteś w lochu na jednym piętrze. Jest skarb, który jest chroniony przez zamknięte drzwi. Drzwi można otworzyć, znajdując odpowiednie klucze. Twoim celem jest znalezienie najkrótszej ścieżki do skarbu.
Wkład
Wejście będzie dwuwymiarową siatką reprezentującą początkowy układ lochu.
###########
#$ # g#
# # ####
###G## #
# ####C#
#c @ #
###########
To ty: @
To są ściany: #
To jest skarb: $
Zamknięte drzwi są wielkimi literami: A
... Z
Każde drzwi mają odpowiadające im małe litery:a
...z
- Zawsze będzie jeden
@
i jeden$
. - Loch zawsze będzie prostokątny.
Nie ma gwarancji, że zewnętrzna krawędź lochu jest ścianą. To jest prawidłowy loch:
$ A## @ a
- Nie ma gwarancji, że skarb jest osiągalny. Niektóre lochy mogą nie być rozwiązane.
- Mogą istnieć drzwi bez klucza i mogą istnieć klucze, które nie otwierają żadnych drzwi.
- Nigdy nie będzie duplikatów drzwi ani kluczy.
Wydajność
Twój program powinien wypisać sekwencję R
, L
, U
, D
(lub 4 inne odrębne symbole) do reprezentowania najkrótszą możliwą drogę do skarbu. Tutaj RLUD
oznacza odpowiednio: prawo, lewo, góra i dół. Jeśli istnieje wiele najkrótszych ścieżek, program musi wydrukować tylko jedną z nich.
- Nie możesz przejść na ścianę.
- Nie możesz poruszać się poza granicami lochu.
- Nie możesz przejść do drzwi bez podniesienia klucza.
- Przejdź na klucz, aby go podnieść.
- Nie trzeba otwierać każdych drzwi.
Jeśli nie można dotrzeć do skarbu poprzez prawidłową sekwencję ruchów, twój program musi zakończyć się bez drukowania niczego. (Końcowy znak nowej linii jest dozwolony.)
Punktacja
To jest golf golfowy, więc wygrywa odpowiedź z najmniejszą liczbą bajtów.
Przypadki testowe
Każdy przypadek testowy będzie miał wysokość i szerokość lochu w pierwszej linii oraz jedną możliwą ścieżkę z optymalną liczbą ruchów w ostatniej linii.
1 2
@$
R (1)
3 3
$
#Z#
@ z
RRLUUR (6)
3 5
c#d#$
#C#D
@
UUDDRRUUDDRRUU (14)
7 16
c # b # ###@
### #
A ##### ####
d # e
B ## #####
### C ##
# a DE $
RDDDDDDL (8)
16 37
#####################################
# #ijk #a M ##m## # # R #
# # # # # ####
###J#### ############# ### # P b#
#e N h # ####
########## ########### ###### #
# # # $ # # # ####
# D H # # # Q f#
# EcF # #####A##### ###### ####
# G # #####B##### # #
# K #####C##### ############
# # #
########### # #### ##### ####
# # p # # n # #
# d # @ # o# r #
#################Z###################
UUULLLLLLDDLLLDLLLLLLRRRRRRRRRUUURRRRRRRRRRRRRRRDDLLRRUULLUUUUUUURRRRRUURRRDRRRLLLLULLLLLDDLLLLUULLLUDLLLLLULLLRRRRRDRRRRRRDDLLLLLLLLLLLLDDDLLLLLLLDURRRRRRRRDDDDRRRRRRUUUUU (172)
Nie można dotrzeć do skarbu w następujących lochach. W tych przypadkach testowych nie powinno być żadnych wyników.
1 3
@#$
7 11
#a#j#$#i#f#
# #E#F#c#H#
# #K#D#A#G#
# #
#C#J# #I#B#
#h#d# #L#g#
#l#e#@#b#k#
10 25
#########################
# fgh # # c B b # #
$ # # # # # #
###### # ##H###E## #
# #
# ######### ##e##
Z @ D y # # #
# ######### F C#
# G # Ad#
#########################
Poniższy fragment kodu może służyć do sprawdzania poprawności odpowiedzi.
function run() {var dungeonText = document.getElementById("dungeon").value;var dungeonLines = dungeonText.split("\n");var height = dungeonLines.length;var width = dungeonLines[0].length;var dungeon = new Array(height);for (i = 0; i < dungeon.length; i++) {var dungeonLine = dungeonLines[i];if (dungeonLine.length != width) {return error("The dungeon is not rectangular");} dungeon[i] = dungeonLines[i].split("");} var movesText = document.getElementById("moves").value;var moves = movesText.trim().split("");var moveCount = moves.length;var rowAt, colAt;for (r = 0; r < dungeon.length; r++) {for (c = 0; c < dungeon[r].length; c++) {if (dungeon[r][c] == '@') {rowAt = r;colAt = c;}}} var treasure = false;while (moves.length > 0) {var move = moves[0];var row = rowAt,col = colAt;switch (move) {case 'R':col++;break;case 'L':col--;break;case 'U':row--;break;case 'D':row++;break;default:return print(dungeon, moves, "Invalid move");} if (row < 0 || col < 0 || row >= height || col >= width) {return print(dungeon, moves, "Out of bounds");} var target = dungeon[row][col];if (target.match(/[A-Z#]/)) {return print(dungeon, moves, "Path blocked");} if (target.match(/[a-z]/)) {var door = target.toUpperCase();for (r = 0; r < dungeon.length; r++) {for (c = 0; c < dungeon[r].length; c++) {if (dungeon[r][c] == door) {dungeon[r][c] = ' ';}}}} if (target == '$') {treasure = true;} dungeon[row][col] = '@';dungeon[rowAt][colAt] = '.';rowAt = row;colAt = col;moves.shift();} if (treasure) {print(dungeon, moves, "Got the treasure in " + moveCount + " moves!");} else {print(dungeon, moves, "Failed to reach treasure");}} function error(message) {var result = document.getElementById("result");result.innerHTML = message;} function print(dungeon, moves, message) {var output = message + "\n";for (r = 0; r < dungeon.length; r++) {for (c = 0; c < dungeon[r].length; c++) {output += dungeon[r][c];} output += "\n";} for (i = 0; i < moves.length; i++) {output += moves[i];} var result = document.getElementById("result");result.innerHTML = output;}
Dungeon:<br/><textarea id="dungeon" name="dungeon" rows="20" cols="40"></textarea><br/>Moves:<br/><textarea id="moves" name="moves" cols="40"></textarea><br/><button id="run" name="run" onclick="run();">Start</button><br/><br/>Result:<br/><textarea id="result" name="result" rows="20" cols="40" disabled></textarea><br/>
źródło
Odpowiedzi:
Perl,
157152151 bajtówZawiera +4 dla
-p0
(nie może być liczone jako rozszerzenie,-e
ponieważ używa'
w kilku miejscach)Uruchom z labiryntem na STDIN:
keymaze.pl
:Zamień
\n
i^H
ich dosłowne wersje dla żądanego wyniku. Potrzebuje około 1 godziny i nieco mniej niż 2 gigabajty na mojej maszynie, aby rozwiązać wielki labirynt.źródło
Java
8-12821277126812591257 bajtówTo przechodzi wszystkie testy. Jednak w przypadku niektórych z nich daje to nieco inne wyniki (gdy istnieje więcej niż jeden optymalny sposób, co nie stanowi problemu).
W przypadku czwartego testu daje to:
Zamiast tego:
W przypadku piątego testu daje to:
Zamiast tego:
Wersja golfowa:
Wersja bez golfa
Cechy:
Przyjmowanie danych wejściowych
Aby go uruchomić, spróbuj tego:
Lub jeśli używasz wersji ungolfed wymienić
G
„szTreasureHunt
.Plik powinien zawierać loch. Dane wejściowe nie powinny kończyć się wierszem. Ponadto akceptuje tylko zakończenia linii w
\n
formacie. To nie będzie działać z\r\n
ani z\r
.Ponadto nie sprawdza ani nie dezynfekuje danych wejściowych. Jeśli dane wejściowe są zniekształcone, zachowanie jest niezdefiniowane (prawdopodobnie spowoduje zgłoszenie wyjątku). Jeśli pliku nie można znaleźć, zostanie zgłoszony wyjątek.
Uwagi
Moja pierwsza implementacja gdzieś w pobliżu 1100 bajtów nie mogła rozwiązać piątego przypadku testowego w rozsądnym czasie. Powodem tego jest to, że moja implementacja brutalnie wymusza wszystkie możliwe permutacje przedmiotów kolekcjonerskich (tj. Klucze i skarb), które są dostępne (tj. Nie są zamknięte w niedostępnym pomieszczeniu).
W najgorszym przypadku, przy wszystkich 26 kluczach i skarbie, byłoby to 27! = 10 888 894 450 418 352 160 768 000 000 różnych kombinacji.
PO nie określił, że odpowiedzią powinno być coś, co zadziałało w rozsądnym czasie. Uważam jednak, że jest to luka, której nie chciałbym wykorzystywać. Postanowiłem więc uruchomić go w odpowiednim czasie dla wszystkich przypadków testowych. Aby to osiągnąć, mój zmieniony program zawiera przycinanie ścieżek wyszukiwania, które okazały się gorsze niż niektóre znane rozwiązania. Ponadto buforuje również subolutions (tj. Programowanie dynamiczne), aby uniknąć ponownego obliczania wielu identycznych lochów, które mogą się pojawić. Dzięki temu jest w stanie rozwiązać 5. przypadek testowy w nieco ponad minutę na moim komputerze.
Rozwiązanie jest rekurencyjne. Chodzi przede wszystkim o to, by poszukiwacz przygód znalazł jakiś przedmiot (klucz lub skarb). W przypadku klucza, po osiągnięciu go przez poszukiwacza przygód, generowany jest nowy podobny loch z usuniętym kluczem i drzwiami, a poszukiwacz przygód przeniósł się tam, gdzie był klucz. Dzięki temu wygenerowane prostsze lochy są rozwiązywane rekurencyjnie do momentu osiągnięcia skarbu lub algorytmu stwierdzenia, że nie ma żadnego osiągalnego przedmiotu. Kolejność odwiedzanych przedmiotów jest brutalnie wymuszona przez przycinanie i buforowanie, jak wyjaśniono powyżej.
Wyszukiwanie ścieżki między poszukiwaczem przygód a przedmiotami odbywa się za pomocą algorytmu przypominającego zarówno wypełnienie zalewowe, jak i Dijkstrę.
Wreszcie podejrzewam, że ten problem jest NP-zupełny (cóż, jego uogólniona wersja bez ograniczenia liczby drzwi / kluczy). Jeśli to prawda, nie oczekuj rozwiązań, które optymalnie rozwiążą bardzo duże lochy z miriadami drzwi i kluczy w rozsądnym czasie. Gdyby dozwolone były ścieżki nieoptymalne, można by je łatwo traktować za pomocą heurystyki (po prostu idź do skarbu, jeśli to możliwe, w przeciwnym razie przejdź do najbliższego klucza).
źródło