A2 - Podmorská jaskyňa

Tajný agent Gejza je na ešte tajnejšej misii, ktorá ho zaviedla do zamínovanej podmorskej jaskyne. Bohužiaľ, nie všetko šlo podľa plánu a míny boli odpálené, pričom do jaskyne začala vtekať voda. Gejza sa teraz snaží zistiť, či sa mu podarí utiecť a ako dlho mu to bude trvať. Keďže však v panike zabudol počítať, musíte mu s touto úlohou pomôcť vy.

Úloha

Jaskyňa je obdĺžnikového tvaru o rozmeroch X a Y, pričom ju vieme rozdeliť na jednotlivé políčka veľkosti 1×1. Z dier po mínach do jaskyne vteká voda a postupne jaskyňu zaplavuje – každé dve minúty sa voda zo všetkých zaplavených políčok rozšíri aj na všetky ich susedné políčka, pokiaľ na nich nie je skalná stena. Zároveň sa Gejza dokáže každú minútu presunúť na susedné políčko, ktoré nie je zaplavené vodou alebo zatarasené skalnou stenou. 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 Gejza stihne uniknúť ešte predtým, než mu voda odreže cestu od jediného východu z jaskyne.

Vstup

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

• # – stena
• . (bodka) – voľná plocha
• o – otvor, ktorým vteká voda do jaskyne, a teda toto políčko je zaplavené už na začiatku
• e – východ z jaskyne
• x – políčko, kde sa Gejza na začiatku nachádza

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

A1

1 ≤ X, Y ≤ 50

A2

1 ≤ X, Y ≤ 500

Výstup

Vypíšte jediné číslo – najkratší čas, za ktorý sa Gejza dokáže dostať k východu z jaskyne. Ak to nie je možné, vypíšte „Neda sa.“ (bez úvodzoviek).

Príklad 1

Vstup:

5 4
...o.
.....
.....
x..#e

Výstup:

Neda sa.

Vysvetlenie:

Gejzov pokus o útek by mohol vyzerať napríklad takto:

...o.
.....
.....
.x.#e

..ooo
...o.
.....
..x#e

..ooo
...o.
..x..
...#e

.oooo
..ooo
..xo.
...#e

Príklad 2

Vstup:

8 6
..o..#.e
x.......
.#......
........
........
.o......

Výstup:

12

Príklad 3

Vstup:

4 1
x.eo

Výstup

Neda sa.