Jesteś podróżnikiem przemierzającym pustynię między dwoma miastami. Nie możesz nosić wystarczającej ilości wody, aby przejść bez zatrzymywania się. To odmiana klasycznej układanki.

Zasady

Pustynia wygląda tak: siatka WxH składająca się głównie z pustej przestrzeni. Oznaczone miejsce Sto miejsce, w którym zaczynasz, Eto miejsce, w którym chcesz zakończyć, a kwadrat oznaczony liczbą N zawiera N jednostek wody. Kwadraty oznaczone .zatrzymaną wodą.

.....................................
........S............................
.....................................
.........7...........................
.....................................
.......................3.............
.....5...............................
................................2....
.....................................
.....................................
.....................................
...............................E.....
.....................................
....................7................
.....................................
.....................................

Zaczynasz w S z 5 jednostkami wody.

Możesz nosić maksymalnie 5 jednostek wody.

Każda kolej

1. przesuń o jedno pole w górę, w dół, w lewo lub w prawo,
2. zużyj 1 jednostkę wody, którą nosisz,
3. podnieś lub upuść pewną liczbę jednostek wody.

Obrót jest zanotowana w ten sposób: (direction)(+|-)(units of water), +wskazuje jesteś podnoszenia wody, -które spadają go.

Przykładowe zwroty:

D+0        Move Down
R+0        Move Right
D+2        Move Down, pick up two units of water.
U-1        Move Up, drop one unit of water.

Jeśli wykonasz te ruchy, zaczynając od litery S w powyższym przykładzie, pustynia będzie wyglądać później.

.....................................
........S............................
.........1...........................
.........5...........................
.....................................
.......................3.............
.....5...............................
................................2....
.....................................
.....................................
.....................................
...............................E.....
.....................................
....................7................
.....................................
.....................................

Nie możesz zebrać więcej wody niż jest na twoim placu. Kiedy podnosisz wodę, odejmij tę liczbę jednostek od liczby płytek.

Możesz zbierać wodę, aby pomieścić maksymalnie 5 jednostek.

Żaden żeton nie może pomieścić więcej niż 9 jednostek, z wyjątkiem S, która zawiera jednostki nieskończoności.

Możesz upuścić tylko tyle wody, ile aktualnie trzymasz.

Woda na ziemi pozostaje niezmieniona, dopóki nie podniesiesz jej ponownie.

Jeśli wrócisz do S, możesz zebrać dowolną ilość wody bez jej wyczerpywania.

Jeśli osiągniesz E, wtedy wygrasz . Nadal wygrywasz, jeśli spożyjesz ostatnią jednostkę wody na E.

Jeśli po swojej turze masz zero wody i nie jesteś na E, umierasz .

Wejście i wyjście

Twój program otrzyma mapę początkową o dowolnym rozmiarze STDINjako grafikę ASCII w powyższym formacie. Możesz założyć, że jest prostokątny, tzn. Wszystkie linie mają tę samą długość, że jest dokładnie jeden Si jeden Ekwadrat, wszystkie linie są zakończone \n, a cały STDIN będzie zgodny z tym wyrażeniem regularnym:/^[SE1-9\.\n]+$/

Twój program zapisze następujące dane wyjściowe do STDOUT:

1. lista ruchów,
2. ostateczny stan mapy.

Możesz wypisać listę ruchów w dowolnym dogodnym formacie.

Ostateczny stan mapy zostanie wydrukowany w tym samym formacie co dane wejściowe, z tym wyjątkiem, że dodatkowo pokaże trasę, którą przeszedłeś przez pustynię , zaznaczając wszystkie odwiedzane kafelki symbolem #, jeśli ten kafelek nie zawiera wody i nie jest S ani E (tj. to jest .).

PRZYKŁADOWE wejście:

.....S.
.......
.......
E......
....8..

PRZYKŁAD zwycięska produkcja:

D+0
D+0
D+0
D+0
L+5
L+0
L+0
L+0
L+0
U+0
.....S.
.....#.
.....#.
E....#.
####3#.

Nietrywialność

Po opublikowaniu kodu opublikuj przykładowe dane wejściowe mapy, dla których Twój kod znajdzie rozwiązanie, które spełnia następujące warunki nietrywialności:

• S i E są oddalone o co najmniej 10 ruchów.
• Każdy kwadrat, który początkowo zawiera N jednostek wody, musi być otoczony ramką o szerokości N, w której znajdują się wszystkie kwadraty .(bez wody, nie S lub E)

PRZYKŁAD

........2.
..........
..........
S.1..2....
..........
..........
........1.
..3.......
.........E

Jeśli zwiększysz ilość wody na dowolnym kafelku, powyższe stanie się banalne.

Wymagania

Prawdopodobnie twój program napotka szereg nieudanych prób, zanim znajdzie rozwiązanie, jeśli w ogóle.

1. Twój program musi ostatecznie rozwiązać wszelkie możliwe do rozwiązania dane wejściowe.
2. Chcę patrzeć, jak umierasz - twój program wyświetli ruchy i ostateczną mapę trasy na śmierć za każdą nieudaną próbę znalezienia rozwiązania.
3. Jeśli napotkasz zwycięskie rozwiązanie, wydrukuj dla niego pełne wyjście i zakończ.
4. Biegaj, aż znajdziesz rozwiązanie, ale nie próbuj dwukrotnie tego samego rozwiązania - wszystkie zgony powinny odbywać się różnymi drogami.
5. Użyj tego wejścia testowego:

(wymaga co najmniej jednego ruchu, aby upuścić bufor wody w pewnym punkcie środkowym).

 S........
 .........
 .........
 ........E

Najkrótszy kod, który jest opublikowany z nietrywialnym wejściem demonstracyjnym, który rozwiązuje, wygrywa.

Perl, 299 + 1 = 300 254 + 1 = 255 bajtów

To prawie na pewno zostanie pokonane przez jeden z języków gry w golfa, gdy ludzie zobaczą mój algorytm :-)

Uruchom z -n(1 bajtowa kara).

Poprzednia wersja nie była w pełni zgodna ze specyfikacją, ponieważ pozostawiała dodatkową wodę na mapie i nie pokazywała jej w ostatecznej wersji mapy; zmieniając algorytm, aby poradzić sobie z tą sytuacją, udało mi się w ten sposób nieco pomniejszyć.

push@a,[split//];($s,$t)=(length$`,$.)if/S/;($e,$f)=(length$`,$.)if/E/}{$_.=$s<$e?($s++,R):$s>$e?($s--,L):$t<$f?($t++,D):($t--,U);$\=reverse$";$".=y/LRUD/RLDU/r.Y.reverse.($"=~y/Y/X/r);$a[$t-1][$s]=~y/./#/;$\.=$s-$e||$t-$f?redo:$_;print map{join'',@$_}@a

Przykład (dodałem podziały wiersza do danych wyjściowych, aby uniknąć potrzeby przewijania i wyświetlania struktury):

MI.....
# .....
# .....
# .....
##### S
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUXDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUUXDDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUXDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUUUYDDDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUXDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUUYDDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUYDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLYRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLYRRRR
 LXR LLXRR LXR LLLYRRR LXR LLYRR LYR LLLLLUUUU

W notacji używane przez program, ruch jest reprezentowany przez L, R, U, i Dna lewo, w górę, w prawo, w dół odpowiednio. Domyślnie po każdym ruchu zbierasz 1 jednostkę wody, ale można to zmienić, dodając postać:

• X: upuść 2 jednostki wody zamiast zbierać 1
• Y: upuść 1 jednostkę wody zamiast zbierać 1
• (tj. spacja): całkowicie uzupełnij wodę (wypływa dopiero po przejściu do S; program wypisuje również spację wiodącą, co ma sens, ponieważ zaczynasz napełniać się wodą)

Jak widać, możliwe jest przekroczenie tej (raczej jałowej) mapy bez żadnych dodatkowych pul. W rzeczywistości można uzyskać dowolną odległość na podstawie tych zasad, na dowolnej mapie, bez pomocy wcześniej umieszczonej wody. Jako taki, ten algorytm po prostu ignoruje wstępnie umieszczoną wodę, co oznacza, że ​​nie muszę marnować bajtów próbując sobie z tym poradzić. Oznacza to również, że nie zobaczysz bota umierającego, przepraszam. Nigdy nie wychodzi poza zasięg, w którym wie, że na pewno przetrwa.

Powodem musimy zarówno Xi Y(i trochę dodatkowego kodu, aby upewnić się, mamy Xw większości strategii, ale od czasu do czasu Yna końcu) jest to, że specyfikacja wymaga ostateczną wersję mapy na wyjściu. Najłatwiejszym sposobem na to jest pozostawienie mapy nietkniętej (poza naszą ścieżką przez początkowo puste kwadraty), zwłaszcza, że ​​kwadrat, który zaczynał się od 9wody, skończyłby 10(łamaniem sztuki ASCII), gdyby trafił na ścieżkę i użyliśmy tylkoXi dlatego musimy znaleźć rozwiązanie, które pozwoli uniknąć zrzucania dodatkowej wody na mapę. Algorytm „naturalnie” zrzuciłby 1 dodatkową jednostkę wody na każdy kwadrat na trasie; dlatego przedostatni czas, jaki odwiedzamy na każdym placu, zmniejszamy ilość wody upuszczonej o 1 za pomocą Y zamiast X, więc podczas naszej ostatniej wizyty spuszczamy kwadrat z powrotem do pierwotnej ilości wody, a nie pozostawiając go nieco bardziej wilgotnego niż na początku.

Odradzam uruchamianie tego na dużej mapie, ponieważ ma on wydajność O (2 ^ n) (chociaż bot nigdy nie umiera z pragnienia, można przypuszczać, że przy takiej strategii umrze z głodu).

Wersja do odczytu:

# implicit with -n: read a line of input into $_
push @a, [split //]; #/ split $_ into characters, store at the end of @a
($s,$t) = (length$`,$.) if /S/; # if we see S, store its coordinates
($e,$f) = (length$`,$.) if /E/  # if we see E, store its coordinates
}{ # Due to -n, loop back to start if there are more lines.

# From here onwards, $" stores the partial solution this iteration;
#                    $\ stores the partial solution last iteration;
#                    $_ stores the path from ($s,$t) to S.
# At the start of the program, $" is a space, $\ and $_ are empty.

$_ .=  # Work out the next step on the path:
  $s < $e ? ($s++,R) # if too far left, move right, record that in $_;
: $s > $e ? ($s--,L) # if too far right, move left, record that in $_;
: $t < $f ? ($t++,D) # if too far up,    move down, record that in $_;
: ($t--,U);          # in other cases we must be too far down.
$\ = reverse $";     # Store last iteration; $" is constructed backwards.
$" .=                # Extend $" by appending
  y/LRUD/RLDU/r .    # the path from ($s, $t) back to S;
  Y .                # a literal 'Y';
  reverse .          # $/ backwards (i.e. the path from S to ($s, $t);
  ($"=~y/Y/X/r);     # a copy of $" with all 'Y' changed to 'X'.
$a[$t-1][$s] =~      # At the current path coordinate,
  y/./#/;            # replace any '.' with '#'.
$\ .=                # Start appending to $\;
  $s-$e||$t-$f?redo  # if we're not at E, abort that and jump back to {{,
: $_;                # otherwise append $_ (the path from S to E).
print map            # For each element of some array
  {join'',@$_}       # output its concatenated elements
  @a                 # specifying that array as @a.
# Implicitly: print $\ (which specifies the sort of newline print uses).