|
Дырявая ткань
(Время: 1 сек. Память: 16 Мб Сложность: 62%)
На столе лежат несколько кусков ткани, не перекрывая друг друга. Эти куски могут иметь дыры, в том числе и настолько большие, что в них может поместиться целый кусок ткани. Был получен чёрно-белый образ поверхности стола, на котором области, покрытые тканью, представлены символами *, а свободные площади – точками. Один кусок ткани, таким образом, представлен 4-связной областью символов *, то есть группой *, соседствующих друг с другом горизонтально или вертикально, но не по диагонали.
.***..***
.*.*.**.*
.***.*.**
*...**.*.
На схеме три куска - один без дыр, а два – с одной дырой каждый: первый площадью 8, второй – площадью 12.
Ваша цель – найти кусок с наибольшим количеством дыр в нём. Дыра – это 4-связная область точек, полностью окружённых символами *. Если несколько кусков имеют одинаковое количество дыр, нужно выбрать кусок минимальной площади.
Входные данные
В первой строке входного файла INPUT.TXT содержатся два числа W и H (1 ≤ W, H ≤ 100), разделённые пробелами. Следующие H строк содержат по W символов каждая. Символы в этих строках – или * (ASCII 42), или точка (ASCII 46).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – площадь минимального из наиболее дырявых кусков. Если нет кусков с дырами, выходной файл должен содержать ноль.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 9 5
.********
.*......*
.*..**..*
.*......*
.******** | 22 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |