Подразделы

Другие разделы

Дата и время

20/12/2024 16:45:03

Авторизация

Зарегистрироваться
Восстановить пароль

Поиск в глубину

Go Scoring Lemmings, Lemmings Everywhere. But Not For Long. Дырявая ткань Покраска лабиринта Удаление клеток

Дырявая ткань

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (4)

На столе лежат несколько кусков ткани, не перекрывая друг друга. Эти куски могут иметь дыры, в том числе и настолько большие, что в них может поместиться целый кусок ткани. Был получен чёрно-белый образ поверхности стола, на котором области, покрытые тканью, представлены символами *, а свободные площади — точками. Один кусок ткани, таким образом, представлен 4-связной областью символов *, то есть группой *, соседствующих друг с другом горизонтально или вертикально, но не по диагонали.

.***..***
.*.*.**.*
.***.*.**
*...**.*.

На схеме три куска — один без дыр, а два — с одной дырой каждый: первый площадью 8, второй площадью 12.

Ваша цель — найти кусок с наибольшим количеством дыр в нём. Дыра — это 4-связная область точек, полностью окружённых символами *. Если несколько кусков имеют одинаковое количество дыр, нужно выбрать кусок минимальной площади.

Ввод

В первой строке содержатся два числа `W` и `H\ (1\ ≤\ W,\ H\ ≤\ 100)`, разделённые пробелами. Следующие `H` строк содержат по `W` символов каждая. Символы в этих строках — или * (ASCII 42), или точка (ASCII 46).

Вывод

Вывести одно целое число – площадь минимального из наиболее дырявых кусков. Если нет кусков с дырами, выходной файл должен содержать ноль.

Пример ввода

9 5
.********
.*......*
.*..**..*
.*......*
.********

Пример вывода

Источник: Far-Eastern quarterfinal, NEERC, 2001