DRŽAVNO NATJECANJE 2015 – Prvi dan natjecanja / Srednja škola, I. podskupina (1. i 2. razred) - 3. zadatak

Mirko i Slavko igraju igru donekle sličnu Čovječe ne ljuti se, osim što se oni ljute te se smiruju proždirući masne kebabe iz obližnjeg ugostiteljskog objekta.

Ploča za igru je pravokutnog oblika te se sastoji od redaka i stupaca. Neka polja na ploči su blokirana, a ostala su slobodna.

Na početku igre, odrede se početno i završno polje.

Mirko i Slavko imaju svatko po jednu figuricu, a obje figurice se na početku igre nalaze na početnom polju.

Igra se sada odvija u nizu koraka - u svakom koraku igrač može pomaknuti svoju figuricu na susjedno slobodno polje (gore, dolje, lijevo, desno) ili je ostaviti na mjestu.

Također, nije dozvoljeno da se nakon nekog koraka obje figurice nalaze u istom polju.

Jedina iznimka od toga je završno polje - dozvoljeno je da se na kraju nekog koraka obje figurice nalaze u završnom polju te tada igra završava.

Mirko i Slavko žele odigrati nekoliko partija.

U svakoj partiji će koristiti istu ploču, ali će odabrati novo početno i završno polje.

Napišite program koji će za svaku partiju odrediti nakon koliko najmanje koraka ona može završiti.

Ulazni​ podaci

U prvom redu nalaze se tri prirodna broja, , i ( , ) međusobno odvojena razmakom, broj redaka i broj stupaca ploče te broj partija koji će Mirko i Slavko odigrati.

Slijedi redova koji opisuju ploču za igru. U -tom od tih redova nalazi se niz od točno znakova koji opisuje -ti redak ploče. Znak ‘#’ (ljestve) označava blokirano polje, dok znak ‘.’ (točka) označava slobodno polje.

Slijedi redova koji zadaju početna i završna polja za pojedine partije.

U svakom od tih redova nalaze se četiri prirodna broja , , , - redak i stupac početnog polja te redak i stupac završnog polja.

Redci su označeni brojevima od 1 do odozgo prema dolje, a stupci brojevima od 1 do slijeva nadesno.

Početno i završno polje će biti različito te će oba odgovarati slobodnim poljima na ploči. Biti će moguće doći od početnog do završnog polja krećući se samo slobodnim poljima.

Izlazni podaci

Potrebno je ispisati redova - u -ti redak potrebno je ispisati traženi najmanji mogući broj koraka da završi -ta po redu zadana partija.

Primjeri test​ podataka

Ulaz

3 4 3
....
.##.
....
1 1 3 4
1 2 1 3
1 1 1 3

Izlaz

5
1
3

Ulaz

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

Izlaz

4
4
5