C. Фрактал илрүүлэгч

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

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

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

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

Бяцхан Вася фрактал зурах маш дуртай.

Эхлээд тэр $2 × 2$ хэмжээтэй тэгш өнцөгт авна. Тэгээд цаасныхаа зарим нүдийг хараар буддаг гэнэ. Тэр будалтаа фрактал хэлбэрээр хийдэг. Анх хүү хоосон цаас аваад дараах алгоритмаар фрактал зурсан байна. Үүнд:

  • Тэр цаасаа дөрвөн тэнцүү хэсэгт хуваана. Энэ үед зарим нүд нь хараар будагдчихсан байгаа.
  • Цагаан нүд бүрийг дөврөн жижиг тэнцүү хэсэгт хуваагаад фрактал хэлбэрээр будна. Хар нүдийг дөрвөн жижиг хар нүдэнд хуваана.

Үүнээс цааш алхам бүрт $2$-р алхамыг давтдаг. Фрактал зурахын тулд дээрх үйлдлийг хэд хэдэн удаа хийдэг. Энэ нь $2$-р үйлдэл ядаж нэг удаа хийгдсэн байх ёстой гэсэн үг. Уг будалтын үр дүнд үүсэх зургийг фрактал гэж нэрлэдэг ажээ. Доорх зурагт $3$ алхмаар фрактал зурсныг үзүүлэв.

Нэг арай Вася ядарчихсан байгаа учраас фрактал зурсангүй. Тэр зүгээр л цаас аваад, $n × m$ хүснэгтэнд хувааж байгаад зарим нүдийг хараар будчихсан.

Одоо тэр будсан зураг дээр хэдэн квадрат хэлбэртэй, фрактал болж чадах зураг байгааг мэдэхийг хүссэн. Ауваагдаагүй нүднүүдээс бүтсэн квадрат нь зөв фрактал үүсгэж байвал түүнийг тоолно.

Оролт

Эхний мөрөнд хүснэгтийн мөр, баганы хэмжээ $n$, $m$ ($2 ≤ n, m ≤ 500$) өгөгдөнө.

Дараагийн $n$ мөр бүрт $m$ тэмдэгт өгөгдөх бөгөөд "." тэмдэгт нь цагаан нүдийг, "*" тэмдэгт нь хар нүдийг тус тус илэрхийлнэ.

Оролтонд "." болон "*" тэмдэгтээс өөр тэмдэгт өгөгдөхгүй.

Гаралт

Дээр өгүүлснээр зөв фрактал хэдэн удаа үүссэн байгаа тоог хэвлэнэ үү.

Орчуулсан: zoloogg

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

Оролт
6 11
......*.***
*.*.*....**
.***....*.*
..***.*....
.*.*.....**
......*.*..
Гаралт
3
Оролт
4 4
..**
..**
....
....
Гаралт
0

Тэмдэглэл

The answer for the first sample is shown on the picture below. Fractals are outlined by red, blue and green squares.

The answer for the second sample is 0. There is no fractal, equal to the given picture.

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