ŠIOM — 3. Domantas ir lentelė

Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: domantas_lentele.in

Rezultatų failas: domantas_lentele.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

3. Domantas ir lentelė

Jūs turite $n$ eilučių bei $n$ stulpelių lentelę. Kiekvienas lentelės elementas yra arba tuščias (žymimas '.' simboliu), arba užblokuotas (žymimas 'X' simboliu).

Du lentelės elementai yra tiesiogiai sujungti, jei jie turi bendrą krašinę.

Du lentelės elementai ( $r_1,c_1$ ) (esantys eilutėje $r_1$ bei stulpelyje $c_1$ ) bei ( $r_2,c_2$ ) yra sujungti, jei egzistuoja tokia elementų seka, kuri prasideda elementu ( $r_1,c_1$ ) bei pasibaigia elementu ( $r_2,c_2$ ) ir kiekvieni du iš eilės einantys sekos elementai yra tiesiogiai sujungti.

Sujungta komponentė - tai toks tuščių elementų rinkinys, jog bet kurie du rinkinio elementai yra sujungti.

Jūsų pagalbininkas Domantas sugeba tam tikroje zonoje sugriauti kliūtis. Tiksliau, jūs galite pasirinkti $k*k$ dydžio kvadratą lentelėje ir Domantas transformuos visus jame esančius užblokuotus elementus į tuščius. Vis dėlto, Domanto pagalbos galite prašyti tik vieną kartą.

Yra įmanoma, jog Domantas nieko nepakeis, jei visi į pasirinktą kvadratą įeinantys elementai bus tušti.

Jums patinka didelės sujungtos komponentės. Jūsų uždavinys - išspausdinti didžiausios sujungtos komponentės dydį po Domanto pagalbos.

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai $n$ , $k$ ( $1\\leqk\\leqn\\leq500$ ).

Sekančiose $n$ eilučių pateikta po $n$ simbolių, apibūdinančių $i$ -tąją lentelės eilutę.

Rezultatai

išspausdinkite didžiausios sujungtos komponentės dydį po Domanto pagalbos.

Pavyzdžiai

Pradiniai duomenys	Rezultatai
5 2 ..XXX XX.XX X.XXX X...X XXXX.	10

Šeštadieninė informatikos olimpiadininkų mokykla

3. Domantas ir lentelė

Pradiniai duomenys

Rezultatai

Pavyzdžiai