Zimne piwnice

Limit pamięci: 64 MB

Archeolog Bajtur dowiedział się, że pod rynkiem w Bajtowie ukryte są średniowieczne piwnice. Udało mu się zdobyć mapę tych piwnic. Mapa jest podzielona na kwadraty. W legendzie mapy wymienione są puste podłogi, ściany, wejścia, wyjścia, skarby i strażnik.

Bajtur prosi Cię o pomoc w ustaleniu najlepszej trasy "zwiedzania" piwnic. Chciałby on zebrać jak najwięcej skarbów i opuścić piwnice, zanim zostanie złapany przez strażnika. W piwnicach jest bardzo zimno, więc jeśli jest wiele tras pozwalających zebrać taką samą liczbę skarbów, to Bajtur chce wybrać taką, która zajmie najmniej czasu.

Bajtur zaczyna w jednym z wejść (wybranym przez siebie) i wykonuje pierwszy ruch. Bajtur i strażnik wykonują ruchy na przemian.

Zarówno Bajtur, jak i strażnik mogą w każdym ruchu przemieścić się na jeden z ośmiu sąsiadujących kwadratów (dozwolone są ruchy na ukos) albo stać w miejscu. Nie mogą przechodzić przez ściany ani wychodzić poza granice mapy, mogą przechodzić przez wszystkie pozostałe kwadraty.

Średniowieczne bajtowskie legendy dokładnie opisują strategię używaną przez strażnika. Otóż strażnik zawsze będzie starał się ruszyć na ten z sąsiadujących kwadratów, który jest najbliżej Bajtura w metryce euklidesowej. Jeśli taki kwadrat jest wyznaczony jednoznacznie, strażnik rusza się właśnie na ten kwadrat, w przeciwnym przypadku strażnik będzie stał w miejscu.

Gdy Bajtur wejdzie na kwadrat ze skarbem, natychmiast go zabiera. Strażnik również może wejść na kwadrat ze skarbem, ale go nie zabiera. Bajtur nie może wejść na kwadrat ze strażnikiem ani na kwadrat sąsiadujący ze strażnikiem. Bajtur może natychmiast uciec z piwnic, jeśli wejdzie na kwadrat, na którym znajduje się wyjście (i nie może on już wejść ponownie do piwnic).

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite i , oznaczające wymiary planszy (, ).

Każdy z kolejnych wierszy zawiera znaków. Wiersze te opisują mapę labiryntu. Puste podłogi są oznaczone znakiem ., ściany znakiem #, skarby znakiem $, wejścia znakiem <, wyjścia znakiem >, a początkowa pozycja strażnika wielką literą alfabetu łacińskiego (w zależności od imienia strażnika).

W labiryncie jest co najmniej jedno wejście, co najmniej jedno wyjście, dokładnie jeden strażnik i co najwyżej 6 skarbów. Zakładamy, że Bajtur jest w stanie uciec z piwnic.

Wyjście

Na wyjście należy wypisać dwie liczby: liczbę skarbów, które można zdobyć, i najmniejszą liczbę potrzebnych ruchów.

Przykład

Dla danych wejściowych:

20 9
....................
.<..................
.......###..........
....###..#.###.###..
....#....#..........
##..#....#..........
>#...............$$.
<#...............$M>
$#..................

poprawną odpowiedzią jest:

3 24

Rozwiązanie wygląda tak (M - Minotaur (strażnik), @ - Bajtur, :, m - poprzednie pozycje):

sytuacja po 8 ruchach:

....................
.:.....@..M.........
..:.:::###.mmm......
...:###:.#.###m###..
....#....#.....m....
##..#....#......m...
>#...............$$.
.#...............$m>
$#..................

sytuacja po 13 ruchach:

....................
.:.....mmmm.........
..:.::m###.mmm......
...:###M.#.###m###..
....#..:.#.....m....
##..#...:#......m...
>#.......@.......$$.
.#...............$m>
$#..................

sytuacja po 24 ruchach:

....................
.:.....mmmm.........
..:.::m###.mmm......
...:###m.#.###m###..
....#..:m#.....m....
##..#...m#......m...
>#.......m.....mm::.
.#........m...m..Mm@
$#.........mmm:::...

Autor zadania: Eryk Kopczyński.