Školsko natjecanje 2011. godine za 1. i 2. razred Srednje Škole - 3. zadatak

Ovaj tjedan u galeriji slika „Enchantress“ izlaže se jedna jako skupa slika, pa su organizatori ove izložbe htjeli učiniti sve da što bolje osiguraju sliku od moguće krađe. Kao jedna od mnogih mjera zaštite, postavili su sigurnosne lasere u izložbenom prostoru.

Sigurnosni laseri rade na način da bilo koja dva lasera koja imaju vidljivu liniju međusobno uspostavljaju vezu. Vezu mogu uspostaviti samo laseri čija je vidljiva linija paralelna sa zidovima galerije. Ukoliko netko (npr. lopov) prođe između lasera i prekine vidljivu liniju, automatski se oglašava alarm.

Organizatore zanima koliko je skupocjena slika zapravo sigurna uz sigurnosne lasere. Zanima ih da li je moguće doći od ulaza u galeriju do slike bez da se aktivira alarm i koliko bi vremena bilo potrebno nekome da to učini. Organizatori će vam pružiti tlocrt galerije, koji je prikazan kao polje u obliku kvadrata na kojem znak '.' označava slobodan prostor, znak '#' označava zid, znak 'L' laser, znak 'U' ulaz u galeriju, a znak 'S' sliku koju žele osigurati.

Lopov može trčati brzinom jednog kvadratića u polju u sekundi. Lopov će se kretati isključivo paralelno sa zidovima galerije. Lopov ne može preći preko polja na kojem je laser ('L') ili zid ('#').

ULAZNI PODACI

U prvom retku se nalaze dva prirodna broja N, M , 1 ≤ N, M ≤ 30, koji predstavljaju visinu i širinu galerije. Zatim se u slijedećih N redova nalazi po M znakova koji predstavljaju polja galerije.

IZLAZNI PODACI

U prvom i jedinom retku potrebno je ispisati broj sekundi koliko je potrebno lopovu da stigne od ulaza do slike. U slučaju da to nije moguće potrebno je ispisati '-1'.

PRIMJERI TEST PODATAKA

ulaz

5 5
##U##
##..L
.S#..
..#.L
.....

izlaz

10

ulaz

4 5
..U..
####.
.S...
.L..L

izlaz

8

ulaz

4 12
.....U......
L...L.######
.S....#.....
....L.......

izlaz

-1

Objašnjenje

Objašnjenje trećeg test primjera: Nije moguće nikako stići od ulaza do slike jer su laseri postavljeni tako da zatvaraju pravokutnik oko slike. Laser (1,0) je spojen s laserom (1,4) koji je također spojen s laserom (3,4).