ściągnij rozwiązanie : Valet Parking (7z)

1. Cel zadania

Parking (Valet Parking) to gra logiczna polegająca na wyprowadzeniu auta zaparkowanego na przepełnionym parkingu.

2. Reguły gry

Każde z aut może poruszać się tylko w przód i w tył. Przeszkodą uniemożliwiającą ruch są ściany oraz inne auta. Celem gry jest znalezienie takiej sekwencji przestawień poszczególnych aut, aby możliwe było wyprowadzenie z parkingu wskazanego auta poprzez wyjazd. Poza momentem wyprowadzania wyróżnionego auta, żadne z aut nie może także znaleźć się w polu stanowiącym wyjazd.

Plansza zawiera opis parkingu wraz z układem samochodów i wskazanym wyjazdem. Możliwe jest także rozmieszczenie aut, przy którym nie istnieje sekwencja ruchów umożliwiająca wyprowadzenie wyróżnionego auta.

Celem projektu jest napisanie programu, który:

• wczyta opis planszy ze standardowego wejścia,
• znajdzie sekwencję ruchów aut,
• wypisze rozwiązanie na standardowe wyjście

3. Opis wejścia/wyjścia

Program wczytuje opis planszy ze standardowego wejścia. Znaczenie znaków jest następujące:

* * (gwiazdka) – ściana,
* ^ (daszek) – wyjazd z parkingu,
* . (kropka) lub   (spacja) – pusta przestrzeń,
* dowolny znak alfanumeryczny – część auta.

Każda plansza jest prostokątna. Ściany i wyjazd znajdują się wyłącznie na obrzeżach planszy (w skrajnych wierszach i kolumnach). Każda plansza ma dokładnie jeden wyjazd. Jedynymi przeszkodami wewnątrz parkingu są pozostałe auta. Każde z aut składa się z przynajmniej dwóch znaków alfanumerycznych ułożonych sąsiadująco w pionie lub poziomie.

Auto, które należy wyprowadzić, składa się z symboli w postaci liter A (wielkie A).

Wyjściem programu powinna być sekwencja par oznaczających przesuwane auto i kierunek jego ruchu, składających się ze znaku określającego auto i kierunek ruchu w postaci jednej z liter n, s, w, e. Wszystkie pary sekwencji wyjściowej muszą być oddzielone białymi znakami. Ostatni ruch sekwencji powinien doprowadzić do „pokrycia się” jednego z symboli wyprowadzanego auta z symbolem określającym wyjazd z parkingu. Jest to jedyna sytuacja, w której auto może znaleźć się w polu wyjazdu.

Jeśli nie istnieje sekwencja wyprowadzająca auto, program powinien wypisać pojedynczą linię linię o treści:

NO

4. Przykład

Przykładowa plansza gry:

*******
*AAAC ^
*   C *
*BB C *
*     *
*******

Rozwiązaniem jest, między innymi, następująca sekwencja:

Cs
Ae
Ae
Ae

Program podczas działania: