SLK1 - Slintačka a krívačka 1

Na základe potvrdeného výskytu slintačky a krívačky na území Slovenska sa zaviedli prísne opatrenia. Farmár Juraj sa rozhodol zavolať veterinára k svojmu dobytku, je dokonca ochotný zájsť po neho autom. Po medializovaných informáciách sa bojí, či by práve cestou od veterinára nemohli doniesť túto chorobu na svoju farmu.

Úloha

Mapa popisujúca aktuálny stav v okolí je obdĺžnikového tvaru o rozmeroch X a Y, pričom ju vieme rozdeliť na jednotlivé políčka veľkosti 1×1. Na niektorých políčkach bola potvrdená slintačka a krívačka, a teda predpokladá sa, že každé dve minúty sa choroba šíri aj na všetky ich susedné (voľné) políčka. Zároveň sa Juraj dokáže každú minútu presunúť na susedné políčko, ktoré nie je zatarasené prekážkou ani potenciálne zasiahnuté. Každé políčko na pozícii (m,n), až na tie okrajové, má 4 susedov – políčka (m+1,n), (m,n+1), (m−1,n), (m,n−1).

Vašou úlohou je zistiť, či Juraj stihne doviezť veterinára na farmu ešte predtým, než mu vírus odreže cestu k jeho farme.

Vstup

Na prvom riadku sa nachádzajú čísla X a Y, šírka a výška mapy. Nasleduje Y riadkov po X znakoch popisujúcich jednotlivé políčka nasledovne:

• # – prekážka
• . (bodka) – voľná plocha
• o – potvrdený výskyt slintačky a krívačky
• f – farma
• x – políčko, kde sa Juraj na začiatku nachádza

Znaky „x“ a „f“ sa na vstupe vyskytujú každý práve raz.

SLK1

1 ≤ X, Y ≤ 50

SLK2

1 ≤ X, Y ≤ 500

Výstup

Vypíšte jediné číslo – najkratší čas, za ktorý sa Juraj dokáže dostať na farmu bez ohrozenia . Ak to nie je možné, vypíšte „Neda sa.“ (bez úvodzoviek).

Príklad 1

Vstup:

5 4
...o.
.....
.....
x..#f

Výstup:

Neda sa.

Vysvetlenie:

Jurajov pohyb by mohol vyzerať napríklad takto:

...o.
.....
.....
.x.#f

..ooo
...o.
.....
..x#f

..ooo
...o.
..x..
...#f

.oooo
..ooo
..xo.
...#f

Príklad 2

Vstup:

8 6
..o..#.f
x.......
.#......
........
........
.o......

Výstup:

12

Príklad 3

Vstup:

4 1
x.fo

Výstup

Neda sa.