Kod zadania: PPP08B Termin rozwiązania zadania: 17 grudnia godz. 12:00 (południe) Jaś stracił wszystkie pieniądze inwestując w pożyczki subprime. Aby zdobyć kapitał, postanowił udać się do Topologicznego Labiryntu po Niezmierzony Skarb. Na dawno nieaktualizowanych stronach Jaś znalazł urywki informacji o Topologicznym Labiryncie. Dowiedział się, że ma on trzy poziomy: Dziwny Prostokąt, Niepokojący Torus i Przerażającą Wstęgę Möbiusa. Sąsiadujące poziomy połączone są schodami. Pierwszy poziom, Dziwny Prostokąt, jest zbudowany na powierzchni prostokąta i wszystkie jego krawędzie są zabudowane (nie ma możliwości wyjścia poza jego krawędź. Drugi poziom (Niepokojący Torus) zbudowany jest na powierzchni torusa. Wyjście poza górny (północny) brzeg "przenosi" Jasia na dolny (południową) brzeg mapy (jego odległość od wschodniego brzegu się nie zmienia). Analogicznie, wyjście poza dolny brzeg przenosi Jasia za górny brzeg. Wyjście poza lewy (zachodni) brzeg przenosi Jasia na prawy (wschodni) brzeg (nie zmieniając odległości od górnego brzegu), zaś przekroczenie prawego brzegu przenosi Jasia na brzeg lewy. Trzeci poziom (Przerażająca Wstęga Möbiusa) jest zbudowany na powierzchni wstęgi Möbiusa. Brzegi górne i dolne są zabudowane (nie można ich przekroczyć). Przekroczenie lewego lub prawego brzegu przenosi Jasia na przeciwną stronę, jednocześnie zamieniając ze sobą kierunek północny i południowy. Powyższe zasady poruszania się dotyczą także promieni świetlnych, a zatem również widoków (np. w przypadku patrzenia przez brzeg mapy). Nikt nie zna dokładnego układu Labiryntu, ale Jasiowi, w trakcie swoich poszukiwań, udało się narysować przybliżoną mapę. Teraz chciałby poćwiczyć "na sucho" poruszanie się w nim, i prosi Ciebie o pomoc. Napisz program umożliwiający zwiedzanie Labiryntu. Program powinien, dla zadanej mapy Topologicznego Labiryntu, wczytywać kolejne komendy (ruch do przodu, skręt w lewo, skręt w prawo, zejście po schodach, wejście po schodach), i tworzyć kolejne "widoki Labiryntu". Każdy pozmiom Labiryntu ma określone wymiary i składa się z kwadratowych pól (wszystkie poziomy mają takie same wymiary). Każde pole może być zajęte (znajduje się w nim ściana), puste (można przez nie swobodnie przechodzić), może zawierać schody w górę lub w dół (można przez nie swobodnie przechodzić i, dodatkowo, na schodach w górę można wejść na wyższy poziom, schodami w dół można zejść na niższy). Każdy widok ma szerokość 32 znaków i wysokość 16 znaków i przedstawia to, co widziałby Jaś stojąc w danym miejscu i patrząc w jednym z czterech kierunków: na wschód, na północ, na zachód lub na południe. Każdy widok składa się z zestawu obrazów ścian i korytarzy. Obraz lewej ściany o wysokości h ma postać: +_ | -. | | | | | | |_-' + tzn. składa się z następujących linii: * jedna linia zawierająca + (plus), _ (podkreślenie), i 2 spacje * jedna linia zawierająca | (pionowa kreska), spacja, - (minus), . (kropka). * h - 4 linii składających się z | (pionowa kreska), dwóch spacji i | (pionowa kreska) * jedna linia zawierająca | (pionowa kreska), _ (podkreślenie), - (minus), '(apostrof) * jedna linia zawierająca + (plus) i 3 spacje Obraz prawej ściany o wysokości h ma postać: _+ .- | | | | | | | `-_| + tzn. składa się z następujących linii: * jedna linia zawierająca dwie spacje, _ (podkreślenie), i + (plus) * jedna linia zawierająca . (kropka), - (minus), spację, | (pionowa kreska) * h - 4 linii składających się z | (pionowa kreska), dwóch spacji i | (pionowa kreska) * jedna linia zawierająca `(odwrócony apostrof), - (minus), _ (podkreślenie), | (pionowa kreska) * jedna linia zawierająca 3 spacje i + (plus) Obraz ściany na wprost o wysokości h i szerokości w ma postać: +-----+ | | | | | | | | | | +-----+ tzn. składa się z następujących linii: * jedna linia zawierająca + (plus), w - 2 znaki - (minus) i znak + (plus) * h - 2 linii składających się z | (pionowa kreska), w - 2 spacji i | (pionowa kreska) * jedna linia zawierająca + (plus), w - 2 znaki - (minus) i znak + (plus) Obrazy lewego i prawego korytarza o wysokości h mają postać: ---- ---- tzn. składa się z następujących linii: * jedna pusta linia * jedna linia zawierająca cztery znaki - (minus) * h - 4 pustych linii * jedna linia zawierająca cztery znaki - (minus) * jedna pusta linia Wyjątkiem jest korytarz o wysokości 4, który ma postać: ____ tzn. składa się z następujących linii: * jedna pusta linia * jedna linia zawierająca cztery znaki _ (podkreślenie) * dwie puste linie Widziany obraz rysujemy w następujący sposób (zakładając, że Jaś patrzy na północ): * wypełniamy widok spacjami * jeżeli pole na północ od pozycji Jasia jest zajęte, rysujemy ścianę na wprost o wysokości 16 i szerokości 32, z lewym górnym rogiem w punkcie (1, 1) i przerywamy rysowanie * jeżeli pole na północny zachód jest zajęte, rysujemy lewą ścianę o wysokości 16 z lewym górnym rogiem w punkcie (1, 1); jeżeli jest puste, rysujemy lewy korytarz o wysokości 16 z lewym górnym rogiem w punkcie (1, 1) * jeżeli pole na północny wschód jest zajęte, rysujemy prawą ścianę o wysokości 16 z prawym górnym rogiem w punkcie (32, 1); jeżeli jest puste, rysujemy lewy korytarz o wysokości 16 z prawym górnym rogiem w punkcie (32, 1) * jeżeli pole odległe o 2 na północ od pozycji Jasia (pole na północ-północ), rysujemy ścianę na wprost o wysokości 12 i szerokości 24, z lewym górnym rogiem w punkcie (5, 3) i przerywamy rysowanie * jeżeli pole na północ-północ-zachód jest zajęte, rysujemy lewą ścianę o wysokości 12 z lewym górnym rogiem w punkcie (5, 3); jeżeli jest puste, rysujemy lewy korytarz o wysokości 12 z lewym górnym rogiem w punkcie (5, 3) * jeżeli pole na północ-północ-wschód jest zajęte, rysujemy prawą ścianę o wysokości 12 z prawym górnym rogiem w punkcie (28, 3); jeżeli jest puste, rysujemy lewy korytarz o wysokości 12 z prawym górnym rogiem w punkcie (28, 3) * jeżeli pole odległe o 3 na północ od pozycji Jasia), rysujemy ścianę na wprost o wysokości 8 i szerokości 16, z lewym górnym rogiem w punkcie (9, 5) i przerywamy rysowanie * jeżeli pole na północ-północ-północ-zachód jest zajęte, rysujemy lewą ścianę o wysokości 8 z lewym górnym rogiem w punkcie (9, 5); jeżeli jest puste, rysujemy lewy korytarz o wysokości 8 z lewym górnym rogiem w punkcie (9, 5) * jeżeli pole na północ-północ-północ-wschód jest zajęte, rysujemy prawą ścianę o wysokości 8 z prawym górnym rogiem w punkcie (24, 5); jeżeli jest puste, rysujemy lewy korytarz o wysokości 8 z prawym górnym rogiem w punkcie (24, 5) * jeżeli pole na północ-północ-północ-północ-zachód jest zajęte, rysujemy lewą ścianę o wysokości 4 z lewym górnym rogiem w punkcie (13, 7); jeżeli jest puste, rysujemy lewy korytarz o wysokości 4 z lewym górnym rogiem w punkcie (13, 7) * jeżeli pole na północ-północ-północ-północ-wschód jest zajęte, rysujemy prawą ścianę o wysokości 4 z prawym górnym rogiem w punkcie (20, 7); jeżeli jest puste, rysujemy lewy korytarz o wysokości 4 z prawym górnym rogiem w punkcie (20, 7) Analogicznie wyglądają procedury rysowania widoku. gdy Jaś patrzy w innych kierunkach (odpowiednio zamieniając kierunki). Innymi słowy, analizujemy cztery pasy szerokości 3 pól, prostopadłe do kierunku patrzenia, od najbliższego Jasiowi. Jeżeli centralne pole jest zajęte (ściana) rysujemy ścianę na wprost w odpowiednim miejscu. Jeżeli pole to jest wolne, rysujemy lewą i prawą ścianę (korytarz) w zależności od tego, czy prawe/lewe pole pasa jest zajęte. Parę przykładów widoków (kolor ciemnoszary to podłoga, kolorami oznaczone są ściany odpowiadające konkretnym polom mapy, jasnoszarym kolorem oznaczono pola nieistotne dla widoku): Zastosowanie powyższej procedury poprawnie narysuje wszystkie widoki (nie będzie danych testowych, które będą prowadziły do nielogicznych czy dziwnych widoków). Podczas rysowania widoku schody należy traktować tak, jak puste pole (widok pustego pola i schodów niczym się nie różni). Przed wyświetleniem, widok należy narysować w pamięci (utworzyć tablicę znaków o wymiarach odpowiadających wymiarom widoku i w niej narysować widok). Dopiero po narysowaniu całego widoku, należy wypisać zawartość tablicy na wyjście. Wejście Na wejściu programu pojawią się kolejno: w h - liczby całkowite, nie większe niż 32, opisujące wysokość i szerokość Labiryntu x y - liczby całkowite, z zakresu <1, 32> oznaczające pole w którym zaczyna Jaś m11m12...m1w m21m22...m2w ... mh1mh2...mhw - napisy opisujące mapę pierwszego poziomu Labiryntu - mij jest jednym ze znaków: * kropką (.) oznaczającą puste pole, * hashem (#) oznaczającym ścianę, * znakiem większości (>) oznaczającym schody w dół, n11n12...n1w n21n22...n2w ... nh1nh2...nhw - napisy opisujące mapę drugiego poziomu Labiryntu - nij jest jednym ze znaków: * kropką (.) oznaczającą puste pole, * hashem (#) oznaczającym ścianę, * znakiem większości (>) oznaczającym schody w dół, * znakiem mniejszości (<) oznaczającym schody w górę o11o12...o1w o21o22...o2w ... oh1oh2...ohw - napisy opisujące mapę trzeciego poziomu Labiryntu - oij jest jednym ze znaków: * kropką (.) oznaczającą puste pole, * hashem (#) oznaczającym ścianę, * znakiem mniejszości (<) oznaczającym schody w górę k - liczba całkowita nie większa niż 8192 oznaczająca liczbę ruchów do wykonania (jednocześnie określa liczbę obrazów do wyświetlenia r1 ... rk - znaki opisujące kolejne kroki; ri może być jednym ze znaków: * n oznacza przejście o jedno pole do przodu, * p oznacza obrót o 90 stopni w prawo, * l (mała litera L) oznacza obrót o 90 stopni w lewo, * < oznacza zejście schodami w dół, * > oznacza wejście schodami do góry, * q oznacza koniec - krok ten wystąpi zawsze ostatni (i tylko jako ostani), więc rk = 'q' Jaś rozpoczyna wędrówkę po Topologicznym Labiryncie patrząc na wschód. Program powinien sprawdzać, czy krok jest możliwy do wykonania (tzn. czy mozna wejść na pole, na które zamierzamy przejść, czy schodząc w dół Jaś stoi na odpowiednich schodach). Jeżeli dany krok jest niepoprawny, nie należy go wykonywać (tzn. pozycja Jasia się nie zmienia). Nie należy jednak pomijać wyświetlania żadnego widoku (w przypadku niewłaściwego kroku efektem będzie wyświetlenie dwóch takich samych widoków). Wyjście Na wyjściu powinno pojawić się k widoków. Każdy widok powinien składać się z 16 linii po 32 znaki. i-ty widok powinien przedstawiać to, co widzi Jaś przed wykonaniem i-tego kroku. Kolejne widoki powinny być rozdzielone pustą linią. Testy Test 1 (6 pkt.) Jaś porusza się tylko po pierwszym poziomie Labiryntu, nie wykonuje niepoprawnych kroków, Test 2 (2 pkt.) Jaś porusza się tylko ko pierwszym poziomie Labiryntu, może wykonywać niepoprawne kroki, Test 3 (2 pkt.) Jaś porusza się po wszystkich poziomach Labiryntu, nie ma konieczności implementowania topologii torusa i wstęgi (brzegi wszystkich poziomów są zabudowane; wszystkie poziomy są równoważne z pierwszym poziomem) Test 4 (5 pkt.) (część rozszerzona) bez ograniczeń Przykład Wejście 8 5 2 2 ######## #.....># ##.#.#.# ##.#.#.# ######## ######## #>....<# ######.# ######.# ######## ######## #<.#...# ##.#.#.# ##...#.# ######## l n r n n n q Wyjście +_ | -. | |+_ _+---- | || -. .- | | || |+_ | | | || || -. | | | || || |+_ _+----| | | || || || -..- | | | | || || ||_-'`-_| | | | || || |+ +----| | | || ||_-' | | | || |+ | | | ||_-' `-_| | |+ +---- |_-' + +------------------------------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | +------------------------------+ +------------------------------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | +------------------------------+ +_ | -. | |+_ _+---- | || -. .- | | || |+_ | | | || || -. | | | || || |+_ _+----| | | || || || -..- | | | | || || ||_-'`-_| | | | || || |+ +----| | | || ||_-' | | | || |+ | | | ||_-' `-_| | |+ +---- |_-' + +_ _+ | -. .- | | |+_ | | | || -. | | | || |+_ _+----| | | || || -. .- | | | | || || |+_ | | | | | || || || -.____| | | | | || || ||_-' | | | | | || || |+ | | | | | || ||_-' `-_| | | | || |+ +----| | | ||_-' | | | |+ | | |_-' `-_| + + +_ | -. | |+_ _+---- | || -. .- | | || |+_ | | | || || -. | | | || || |+------+----| | | || || || | | | | || || || | | | | || || |+------+----| | | || ||_-' | | | || |+ | | | ||_-' `-_| | |+ +---- |_-' + +_ _+ | -. .- | | |+_ | | | || -. | | | || |+--------------+----| | | || || | | | | || || | | | | || || | | | | || || | | | | || || | | | | || || | | | | || |+--------------+----| | | ||_-' | | | |+ | | |_-' `-_| + +