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

U nadaleko poznatoj zemlji Nigdjezemskoj sukobile se dvije vojske, vojska X i vojska Y.

Vojnici dviju sukobljenih strana nalaze se na dvodimenzionalnoj mapi od N redova i M stupaca ( 2 <= N, M <= 1000). Cilj vojske X je ukrasti zastavu vojske Y (zastava je na mapi označena sa znakom F) i zatim se zajedno okupiti na bilo kojem polju na mapi da proslave svoju pobjedu.

Vojska X je odlučila provesti misiju „Vrana“ svrha koje je ukrasti zastavu bez da to primijete vojnici vojske Y. Stoga oni žele , u svakom trenutku za vrijeme trajanja misije, da udaljenost od bilo kojeg vojnika vojske X do njemu najbližeg vojnika vojske Y bude veda ili jednaka R. Svaki vojnik se u jednom koraku smije kretati samo za jedno polje u smijeru gore, dolje, lijevo ili desno. Udaljenost od polja A do polja B se određuje kao broj koraka koji je potreban zamišljenom vojniku na polju A da dođe do polja B.

Pomozite generalu vojske X da odredi najvedi mogudi takav R pri kojem je mogude ostvariti misiju (ukrasti zastavu i proslaviti svoju pobjedu okupljanjem na bilo kojem odabranom mjestu).

ULAZNI PODACI

U prvom retku nalaze se dva cijela broja N, M (broj redaka i stupaca matrice) . Zatim slijedi N redaka koji opisuju mapu. U svakom retku znak točke označava prazno polje mape, znakovi X i Y označavaju vojnike i znak F označava zastavu.

IZLAZNI PODACI

U jednom retku jedan cijeli broj koji označava najmanju mogudu vrijednost za broj R.

PRIMJERI TEST PODATAKA

ulaz

4 4
...F
.Y..
...X
X...

izlaz

2

ulaz

4 4
.Y.F
.Y..
..YY
X...

izlaz

0

ulaz

4 4
.Y.F
.Y..
..X.
X...

izlaz

2