B1 - Podmorská jaskyňa II.

V minulom kole sme pomáhali tajnému agentovi Gejzovi utiecť z jaskyne, ktorá sa postupne zapĺňala vodou. Nejakým šťastím sa mu pri tom podarilo zablúdiť do miestnosti s truhlicou plnou diamantov, ktorá je však príliš ťažká na to, aby ju odniesol celú sám. Preto stojí pred neľahkým rozhodnutím - má si začať napchávať vrecká diamantami, alebo radšej utekať pred valiacou sa vodou?

Úloha

Jaskyňa má štvorcový pôdorys veľkosti N×N. Každé políčko veľkosti 1×1 má špeciálny význam:

• # – stena, ktorou neprejde voda ani Gejza
• . (bodka) – voľná plocha
• o (malé písmeno "o") – otvor, ktorým vteká voda do jaskyne
• e – východ z jaskyne
• x – políčko, kde sa nachádza truhlica (a teda aj Gejza)

Každú minútu sa udeje niekoľko vecí:
Najskôr sa Gejza rozhodne, či si bude ďalej brať diamanty z truhlice, alebo sa vydá ná útek. Počas tejto minúty svoje rozhodnutie už nemôže zmeniť a ak sa raz rozhodne utekať, už sa nemôže k truhlici vrátiť. Pri úteku môže Gejza v každej minúte spraviť najviac H krokov. Jeden krok znamená, že sa presunie na voľné susedné políčko - to je políčko, ktoré hranou susedí s tým súčasným.
Na konci každej minúty sa rozšíri voda, teda pod vodou sa ocitne každé voľné políčko, ktoré susedí s už zatopeným políčkom. V čase 0 sú zatopené len políčka označené písmenom "o".
Gejza sa utopí, akonáhle sa ocitne na zatopenom políčku alebo je zatopené políčko, na ktorom stojí. Východ z jaskyne nemôže byť zatopený.
Vašou úlohou je zistiť, koľko najviac minút môže Gejza stráviť pri truhlici s diamantami, aby stihol bezpečne uniknúť.

Vstup

Na prvom riadku vstupu sú čísla N a H oddelené medzerou - rozmer jaskyne a počet krokov, ktoré Gejza spraví za minútu. Nasleduje N riadkov o N znakoch popisujúcich jaskyňu. Znaky „x“ a „e“ sa na vstupe vyskytujú každý práve raz. Naviac je na vstupe aspoň jeden znak „o“ a platí, že existuje cesta od nejakého otvoru k truhlici. To znamená, že ak by Gejza čakal pri truhlici dostatočne dlho, nakoniec by sa k nemu dostala voda.

Výstup

Na výstup vypíšte jedno číslo - najdlhší čas v minútach, aký môže Gejza stráviť pri truhlici tak, aby následne ešte stihol opustiť jaskyňu. Ak neexistuje spôsob ako uniknúť, vypíšte -1.

B1

1 ≤ N ≤ 50

H=1

B2

1 ≤ N ≤ 800

1 ≤ H ≤ 1000

Príklad 1

Vstup:

7 3
#######
#.....#
#.....#
x.....e
#.....#
#.....#
#ooooo#

Výstup:

1

Príklad 2

Vstup:

7 3
#######
#.....#
#.....#
x.....e
#.....#
#.....#
#.oo..#

Výstup:

2