C - Cibulky

Č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 ]

Janko sa rozhodol, ze zacne podnikat. Rad by predaval cibulky. A aby mal v tvrdom konkurencnom boji sancu, musi mat svoje policko co najlepsie obhospodarovane. Taktiez by rad usetril na platoch, preto sa rozhodol, ze o jeho policko sa bude starat robot, ktory nechce ziaden plat (iba palivo) a dokaze robit nepretrzite. Ulohou robota bude polievat zahony. Janko ma svoje policko rozdelene na N x M casti. Kazda cast je bud plot, cesta alebo zahon. V kazdom zahone je zabudovany senzor vlhkosti, ktory je pravidelne kontrolovany hlavnym pocitacom. Ak pocitac zisti, ze niektory zo zahonov potrebuje vodu, vysle prikaz robotovi. Ten na zadane policko pride a zaleje ho. Kedze ale pocitac je uz starsi a je poruchovy, obcas zada robotovi chybnu poziciu zahonu (bud to nie je zahon, alebo je to v casti, kam sa robot nevie kvoli plotom dostat). Preto je potrebne takyto prikaz ignorovat, aby sa zbytocne neminalo palivo.

Uloha

Vasou ulohou je zistit, kolko paliva minie robot za jeden den. Na zaciatku dna sa robot nachadza na vychodzej pozicii. Potom dostava prikazy od pocitaca. Bud sa prikaz neda vykonat, vtedy ho robot ignoruje. Ak sa prikaz vykonat da (policko je dostupne a je to naozaj zahon), robot tam prejde a caka na dalsie prikazy. Robot musi chodit vzdy tou najkratsou cestou. Moze pritom chodit po ceste, alebo aj po zahonoch. Robot vie prejst z jedneho policka na druhe len ak susedia hranou (vie sa pohybovat do 4 smerov). Nesmie vojst na policko, na ktorom je plot. Prechod z jedneho policka na druhe stoji vzdy 1 mililiter paliva. Na konci dna sa robot presune nazad na vychodie policko. Robot nesmie vyjst mimo policka.

Vstup

Prvy riadok vstupu obsahuje dve cele cisla N a M, vyska a sirka policka. 1 ≤ N,M ≤ 50. Dalsi riadok obsahuje dve cele cisla Y a X, suradnice vychodzieho policka robota. 1 ≤ Y ≤ N, 1 ≤ X ≤ M. Nasledujucich N riadkov obsahuje po M znakov. Znaky su bud # - plot, . - cesta, @ zahon s cibulkami. Dalej nasleduje cislo C, pocet prikazov, 1 ≤ C ≤ 50. Za nim nasleduje C riadkov obsahujucich cisla A a B, poziciu v ramci policka, kam sa ma robot presunut (nie kazda musi byt dosiahnutelna).

Vystup

Vypiste jediny riadok obsahujuci potrebne palivo v mililitroch.

Priklad

Vstup:

4 4
1 1
..@.
..@@
####
@...
5
1 1
2 2
4 1
2 3
1 3

Vystup:

Vysvetlenie:

Prve dva prikazy robot ignoruje, lebo na zadanych poziciach je cesta. Treti prikaz tiez ignoruje, lebo sa na danu poziciu nemoze dostat. Stvrty prikaz vykona a spotrebuje pritom 3 mililitre paliva. Piaty prikaz vykona a spotrebuje 1 mililiter paliva. Nakoniec sa este musi presunut na vychodziu poziciu a na to potrebuje 2 mililitre paliva.

Problem by Samuel BWPOW Kupka

DS2004