AL - ALgoritmy

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Matilda si zapísala predmet Programovanie, algoritmy a zložitosť. Na prednáške preberali algoritmy prehľadávania grafu, tak si svoje prográmatorské zručnosti chce overiť na staršom výrobku UPJŠ - robotovi ALadárovi. Vytvorila pre neho programy, ale nevie ako dlho budú trvať.

Úloha

Robot Aladár je veľmi jednoduchý. Po umiestnení do miestnosti prijíma inštrukcie na otočenie okolo vlastnej osi a následný pohyb dopredu o konkrétny počet krokov. Otočiť sa vie len doprava alebo doľava o 90 stupňov. Ak počas posúvania sa dopredu narazí do steny, nacúva na miesto, na ktorom stál pred vykonávaním danej inštrukcie. Vo svojej vnútornej pamäti si pamätá počet krokov, ktoré počas celého programu prešiel a tie po skončení oznámi autorom. Tvojou úlohou je teda vytvoriť program, ktorý načíta mapu miestnosti, začiatočnú pozíciu Aladára a zoznam inštrukcií. Výsledkom má byť počet krokov, ktoré by mal Aladár absolvovať v prípade, že naozaj robí to, na čo bol naprogramovaný.

Vstup

Prvý riadok vstupu obsahuje dve celé čísla M a N, 1 ≤ M,N ≤ 100, M reprezentuje výsku mapy (počet riadkov) a N šírku mapy (počet stĺpcov). Ďalej nasleduje M riadkov, každý obsahujúci N znakov # (záhradka) alebo . (bodka), pričom záhradka označuje stenu a bodka voľný priestor. Môžeš predpokladať, že mimo mapy sa všade nachádza stena. Ďalší riadok obsahuje tri prirodzené čísla Y,X a P, 1 ≤ Y ≤ M, 1 ≤ X ≤ N, 1 ≤ P ≤ 100. Pričom Y a X označuju začiatočnú pozíciu robota na mape, Y je riadok a X je stĺpec. Môžes predpokladať, že robot začína vždy na prázdnom políčku a pozerá sa smerom dohora (smerom k hornému okraju mapy). Ďalších P riadkov obsahuje po jednom zamýšlanom kroku robota. Každý riadok má formát L alebo P, otočenie robota pred vykonaním krokov doľava alebo doprava a prirodzené číslo oddelené medzerou, označujúce počet krokov, ktoré chce robot v tomto smere vykonať. Presný popis vstupu si pozri na príklade.

Výstup

Výstupom má byť jediný riadok s počtom krokov, ktoré robot Aladár prejde.

Príklad

Vstup:

10 10
##########
#.###...##
#.###...##
#........#
##.......#
####.....#
#####....#
..........
#.....####
###.######
7 7 5
L 10
L 1
L 3
P 5
P 5

Výstup:

Vysvetlenie:

Robot sa najprv pozerá hore a stojí na pozícii (7,7). Na základe prvej inštrukcie sa otočí doľava a pokúsi sa ísť 10 krokov. Po jednom kroku však narazí do steny a tak sa vráti na pôvodnú pozíciu (spolu 2 kroky). Opäť sa otočí doľava a pojde o jeden krok smerom nadol (spolu 1 krok). Opäť sa otočí doľava, takže teraz smeruje doprava a pôjde 3 kroky (spolu 3 kroky). Teraz stojí na samom okraji mapy na riadku 8 a pozerá doprava. Otočí sa doprava a pokúsi sa ísť 5 krokov. Po ním je však hneď stena, takže zostane na mieste (spolu 0 krokov). Opäť sa otočí doprava a pôjde 5 krokov (spolu 5 krokov). Takže skončil na políčku (8,5) a prešiel spolu 11 krokov.

22 Domáce 1