C. Баавгай ба квадрат хүснэгт

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд $n$ мөр болон $n$ багана бүхий нэгэн хүснэгт байжээ. Хүснэгтийн нүд болгон нь хоосон ('.'-ээр тэмдэглэнэ) эсвэл хориглогдсон ('X'-ээр тэмдэглэнэ) байв.

Хэрэв 2 хоосон нүд нь ерөнхий талтай байвал тэдгээрийг шууд холбогдсон байна гэж үзнэ. $(r_{1}, c_{1})$ ($r_{1}$ мөр болон $c_{1}$ баганад байрлалтай нүд) болон $(r_{2}, c_{2})$ гэсэн 2 нүднүүдийн хувьд хэрэв $(r_{1}, c_{1})$-аас эхлээд $(r_{2}, c_{2})$ дээр дуусах ямар ч 2 дараалсан нүднүүд нь шууд холбогдсон байх хоосон нүднүүдийн дараалал оршин байвал эдгээрийг холбогдсон нүднүүд гэж үзэх юм.

Холбогдсон бүрэлдэхүүн хэсэг гэдэг нь хэсэг хоосон нүднүүдийн олонлогийг хэлэх бөгөөд ингэхдээ бүрэлдэхүүн хэсэг доторх ямар ч 2 нүд нь холбогдсон байх ёстой ба уг олонлог доторх ямар ч нүд нь уг олонлогоос гаднах ямар нэгэн нүдтэй холбогдоогүй байх ёстой юм.

Таны найз Лимак нь хүрэн баавгай юм. Тэрээр ямар нэгэн хэсэг доторх бүх саадыг устгаж чадах ажээ. Илүү дэлгэрэнгүй тайлбарлавал та хүснэгтийн $k × k$ хэмжээ бүхий нэг квадратыг сонгох бөгөөд Лимак уг квадрат доторх бүх хориглогдсон нүднүүдийг хоосон нүд болгон хувиргах юм. Харамсалтай нь та Лимак-аас зөвхөн ганц удаа л тусламж гуйж болох байв.

Таны сонгох квадрат нь бүтнээрээ уг хүснэгтэн дотор байх ёстой юм. Түүнчлэн Лимак юу ч өөрчлөхгүй байж болох бөгөөд ингэсэн тохиолдолд таны сонгосон квадратын бүх нүд нь аль хэдийн хоосон байсан гэсэн үг юм.

Та том холбогдсон бүрэлдэхүүн хэсэгт дуртай байв. Лимак танд тусалсны дараах хүснэгт доторх хамгийн том холбогдсон бүрэлдэхүүн хэсгийн боломжит хамгийн том хэмжээ хэд вэ?

Оролт

Эхний мөрөнд харгалзан хүснэгтийн хэмжээ болон Лимак-ийн устгаж чадах хэмжээг илэрхийлэх 2 бүхэл тоо $n$ болон $k$ ($1 ≤ k ≤ n ≤ 500$) өгөгдөнө.

Дараагийн $n$ мөрийн мөр болгонд $n$ ширхэг тэмдэгт бүхий нэг тэмдэгт мөр өгөгдөх ба энэ нь хүснэгтийн $i$-дахь мөрийг илэрхийлнэ. Тэмдэгт болгон нь '.' эсвэл 'X' байх ба эдгээр нь харгалзан хоосон нүд болон хориглогдсон нүдийг илэрхийлэх юм.

Гаралт

Лимак-ийн тусламжийг авсны дараах хамгийн том холбогдсон бүрэлдэхүүн хэсгийн боломжит хамгийн том хэмжээг (нүдний тоог хэвлэнэ) хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
5 2
..XXX
XX.XX
X.XXX
X...X
XXXX.
Гаралт
10
Оролт
5 3
.....
.XXX.
.XXX.
.XXX.
.....
Гаралт
25

Тэмдэглэл

Эхний жишээнд та $2 × 2$ хэмжээтэй квадратыг сонгох юм. Доор дүрслэгдсэн зүүн талын зургийн улаан хүрээтэй квадратыг сонгох нь оновчтой сонголт байх бөгөөд ингэснээр та $10$ нүдтэй холбогдсон бүрэлдэхүүн хэсэгтэй болох ба энэ нь баруун талын зурагт цэнхрээр тэмдэглэсэн байна.

Сэтгэгдлүүдийг ачааллаж байна...