eolymp
bolt
Try our new interface for solving problems
Məsələlər

Reklam lövhəsi

Reklam lövhəsi

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122 MiB

Öz yeni məhsulunu Çində reklam etmək üçün bir şirkət göydələndə reklam lövhəsi yerləşdirmək qərarına gəldi. Reklam lövhəsi n sətir və m sütunlu düzbucaqlı tor formasında təşkil edilmiş lampalardan ibarətdir. İstənilən anda lampalardan hər biri ya yandırılmış, ya da söndürülmüş ola bilər.

Reklam məlumatı bir-birinin ardınca göstəriləcək k sayda heroqlif ehtiva edir. Hər bir heroqlif üçün bu heroqlifin əks olunması zamanı hansı lampaların qoşulacağı məlumdur. Digər lampalar isə sönmüş olmalıdır.

Reklam lövhəsini idarə etmək üçün xüsusi sistem hazırlanır. Sistem lampaları tam qruplar şəklində yandıra və söndürə bilər. Bütün lampalar bir neçə qrupa elə bölünür ki, hər bir heroqlifdə bir qrupda olan lampaların ya hamısı yanmış, ya da sönmüş olmalıdır.

İdarəetmə sisteminin işini optimallaşdırmaq üçün lampaları minimal sayda belə qruplara bölmək lazımdır. Reklam bölməsinin əməkdaşlarına bu məsələni həll etməkdə kömək edin.

Giriş verilənləri

Giriş faylının ilk sətrində reklam məlumatındakı heroqliflərin sayını, reklam lövhəsinin yüksəklik və genişliyini ifadə edən k, nm (1k, n, m100) ədədləri verilir.

Sonra k \* n sətirdə heroqliflərin təsviri verilir. Hər bir k heroqlifi m sətrin hər birində n sətirlə verilir. Bu sətirlərin hər biri yalnız "\*" və "." işarələrini ehtiva edir. "\*" yanan, "." isə sönən lampaya uyğundur.

Çıxış verilənləri

Lampaların bölünməsi mümkün olan qrupların minimal sayını verin.

Misalın şərhi

Verilmiş misalda lampaları növbəti şəkildə qruplara bölmək olar: Birinci sütunun iki lampası bir qrupu təşkil edir, sonuncu sütunun iki lampası ikincini, qalan iki lampanın hər biri ayrıca qrup təşkil edirlər.

Nümunə

Giriş verilənləri #1
3 2 3
*..
*..
**.
*..
...
.*.
Çıxış verilənləri #1
4
Mənbə 2012 XIII Всероссийская командная олимпиада школьников по программированию, 25 ноября, Задача А