eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Дирява тканина

Дирява тканина

На столі лежить декілька шматків тканини, не перекриваючи один одного Ці шматки можуть мати дирки, у тому числі і настільки великі, що в них може поміститись цілий шматок тканини. Було отримано чорно-білий образ поверхні столу, на якому області, покриті тканиною, подано символами *, а вільні площі - точками. Один шматок тканини, таким чином подано \textbf{4}-зв'язною областю символів *, тобто групою *, сусідніх одна з одною горизонтально або вертикально, але не по діагоналі. .***..*** .*.*.**.* .***.*.** *...**.*. На схемі три шматки - один без дир, а два - з однією диркою кожен: перший площею \textbf{8}, другий - площею \textbf{12}. Ваше завдання - знайти шматок з найбільою кількістю дир у ньому. Дирка - це \textbf{4}-зв'язна область точок, повністю оточена символами *. Якщо декілька шматків мають одинакову кількість дир, потрібно вибрати шматок мінімальної площі. \InputFile У першому рядку міститься два числа \textbf{W} і \textbf{H}, відокремлених пропусками. Наступні \textbf{H} рядків містять по \textbf{W} символів кожен. Символи у цих рядках або *, або точка. \textbf{1} ≤ \textbf{W}, \textbf{H} ≤ \textbf{100}. \OutputFile Вивести одне ціле число - площу мінімального з найбільш дирявих шматків. Якщо немає шматків з дирами, вихідний файл повинен містити нуль.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
9 5
.********
.*......*
.*..**..*
.*......*
.********
Вихідні дані #1
22