Državno natjecanje 2011. godine za 3. i 4. razred Srednje Škole - 3. zadatak - 1. dan

Kao što je to poznato svim gledateljima Nodne More, Laki je 35 godina radio u tvornici čokolade Kraš, i svakog dana bi pojeo po jednu čokoladu Dorina. Željko Malnar, voditelj Nodne More, izračunao je da je Laki u svom životu sigurno pojeo preko pola tone čokolade. Morate priznati da takvo što ni vama ne bi bilo mrsko!

Za potrebe ovog zadatka moramo se vratiti vremeplovom u prošlost, do jednog davnog dana u tvornici čokolade Kraš, kada je Laki odrađivao nodnu smjenu čuvara skladišta čokolade. Laki je ved dugo godina bio radio u tvornici, pa poznaje skladište napamet. Skladište je podijeljeno na kvadrate i ima oblik kvadratne mreže. Po skladištu se nalaze mnoge zatvorene kutije čokolada i drugih slatkiša i te kutije čine prepreku pri kretanju. Na jednom mjestu se u skladištu nalazi stol, i na njemu je Lakijeva čokolada Dorina.

Tog dana dogodila su se, za Lakija, dva nesretna događaja. Radnici su u skladište donijeli još jednu kutiju slatkiša i stavili je na neki kvadrat. Laki je upoznat s tom činjenicom, ali ne zna na koje mjesto je donesena ta nova kutija. Da situacija bude još gora, te večeri je nestalo struje pa u skladištu nema svjetla.

Laki poznaje skladište napamet, pa mu nedostatak svjetla ne bi bio problem kad bi znao gdje se nalazi ta nova kutija slatkiša. Ovako, bez svjetla, Laki de primijetiti novu kutiju tek u trenutku kada se nađe u kvadratu neposredno pored kvadrata s novom kutijom (dakle, u susjednom kvadratu, a susjedni kvadrati su oni koji imaju zajednički brid). Laki se može kretati samo po kvadratima u kojima se ne nalaze kutije, i to iz nekog kvadrata u njemu susjedni.

Dodatno, kvadrat u kojem se nalazi Lakijeva Dorina je sigurno uvijek prazan, radnici u njega nikada ne ostavljaju kutije. Također, radnici su mislili na Lakija, pa put do njegove Dorine sigurno postoji.

Pomognite Lakiju da što kradim putem dođe do svoje Dorine, bez obzira na to gdje su radnici ostavili novu kutiju

ULAZNI PODACI

U prvom retku, cijeli brojevi x i y, 2 <= x <= 60 i 2 <= y <= 60.

U idudih y redaka, plan skladišta od dana prije (dakle, prije nego što su radnici donijeli novu kutiju). Pritom znak točke označava prazan kvadrat, malo slovo x označava kvadrat kroz koji se ne može prodi, D označava kvadrat u kojem se nalazi čokolada Dorina, a L označava mjesto gdje se nalazi Laki.

IZLAZNI PODACI

U jednom retku, jedan cijeli broj koji označava najkradi put prema opisanim pravilima.

PRIMJERI TEST PODATAKA

ulaz

8 5
.L......
........
x.xxxx..
........
.D......

izlaz

16

ulaz

8 5
.L......
........
x.x.x.x.
........
.D......

izlaz

10

ulaz

10 10
.L........
.xx.......
..........
.x.x.x....
.x.x.x....
.x.x.x....
.x.x.x....
.x.x.x....
..........
D.........

izlaz

22