Županijsko natjecanje 2014. godine za 1. i 2. razred Srednje Škole - 4. zadatak

Mirko je iznajmio slona preko interneta, pa putuje Saharom na svome slonu. On se svaki dan želi pomaknuti za jedno polje (gore, dolje, lijevo ili desno). Mirko zna da se njegov slon, kao i svaki drugi slon, izuzetno boji miševa, pa Mirko nikako ne želi prodi poljem gdje ih ima, jer bi to moglo kritično završiti.

Mirko je slona iznajmio na neviđeno, pa mu nisu rekli da je slon malo čudan. Naime, slon prvih T polja sve Mirkove želje ispunjava, ali nakon toga uđe u nekakav neposlušni dio koji traje sve dok slon ne pređe P narednih polja. U neposlušnom dijelu, slon se također krede u smjeru u kojem Mirko želi, međutim, na točno jednom od tih P polja, slon de jednom stati (a Mirko ne zna kada) i točno se P dana nede pomicati s mjesta, pa makar i bio na kranjem mjestu gdje Mirko želi stidi. Nakon što je prešao tih P polja, ponovo de T polja biti poslušan, pa de sljededih P polja biti neposlušan itd.

Pustinjska klima nije ni malo ugodna. Pustinjom se izmjenjuju sunce i hlad. Na suncu je jako vrude, a u hladu jako hladno. Mirko kada je kretao na put, nije se baš najbolje pripremio, pa uzastopno može izdržati najviše maxT dana na suncu, ili uzastopno najviše MaxT dana u hladu.

Kada je iznajmljivao slona, Mirku su dali i kartu pustinje na kojoj je svako polje označeno jednim od tri znaka:

• '#' – na polju ima miševa, pa je polje neprohodno
• '.' – prohodni dio pustinje koji se nalazi na suncu
• '$' – prohodni dio pustinje koji se nalazi u hladu

Mirko želi dodi na željeno mjesto u pustinji, ali nikako ne želi biti u opasnosti da strada ako ima miševa ili ako bi spletom okolnosti mogao previše uzastopnih dana provesti na suncu ili u hladu.

Ako su poznate Mirkova početna pozicija i mjesto na koje želi dodi, napišite program koji računa duljinu najkradeg puta, na kojem nede biti opasnosti. Ukoliko takav put ne postoji, program treba vratiti -1.

ULAZNI PODACI

U prvom retku nalaze dva broja N, M (1 ≤ N, M ≤ 50), visina i širina pustinje.

U slijededem retku su tri broja T, P, MaxT (1 ≤ T, P, MaxT ≤ 20).

U tredem i četvrtom retku nalaze se po dva broja (N1, M1) i (N2, M2), (0 ≤ N1, N2 < N i 0 ≤ M1, M2 < M) koordinate Mirkove početne pozicije i koordinate mjesta na koje želi doći.

U slijededih N redaka se nalazi po M znakova koji predstavljaju svako polje pustinje.

Napomena: Mirkova početna pozicija i mjesto na koje želi stidi nede nikada biti na istom polju ni na neprohodnom polju. Koordinata (0,0) nalazi se u gornjem lijevom kutu.

Ukoliko npr. Mirko krede s pozicije (0, 0) i treba dodi na poziciju (1,0), a na toj poziciji sija sunce, neovisno o tome je li na poziciji (0, 0) bilo sunce ili hlad, duljina puta je 1, i on je jedan dan proveo na suncu.

IZLAZNI PODACI

U prvi i jedini redak treba ispisati duljinu najkradeg puta na kojem ne vrebaju opasnosti.

PRIMJERI TEST PODATAKA

ulaz

3 5
4 3 6
0 0
2 3
...$.
.###.
....$

izlaz

7

ulaz

7 4
2 3 6
0 0
6 2
....
..$.
....
..$.
....
..$.
....

izlaz

8

ulaz

6 6
1 3 5
0 0
5 0
...$.$
$.....
...$..
......
......
..$..$

izlaz

-1

$$$Objašnjenje

Pojašnjenje drugog test primjera: Mirko može idi preko sljededih polja:

(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2) -> (5,2) -> (6,2)

Tijekom putovanja prodi de kroz dva neposlušna dijela i dvaput stajati.

U zagradama su koraci unutar neposlušnog dijela: 1, 2, 3, 4, 5, 6+, 7, 8, 9, 10, 11+, 12