Кондитерская ACM
Эмбер Клаес Маес, кондитер, открыла свой магазин в прошлом месяце. Чтобы привлечь внимание к своему бизнесу, она решила участвовать в Международном конкурсе кондитеров по шоколаду и разработала рецепт сладких шоколадных плиток. После множества экспериментов она наконец нашла идеальный рецепт. Однако, чтобы придать шоколаду аккуратную прямоугольную форму, требуется высокий уровень мастерства. К сожалению, она снова получила плитку странной формы, как показано на Рисунке 1.
Рисунок 1: Шоколадная плитка странной формы
Каждая плитка состоит из множества маленьких прямоугольных сегментов шоколада. Соседние сегменты разделены бороздками для удобства разлома. Эмбер планировала разрезать плитки странной формы на несколько прямоугольных кусочков и продавать их в своем магазине. Она хочет разрезать каждую плитку следующим образом:
Разрезать плитку вдоль бороздок.
Разрезать плитку на прямоугольные кусочки.
Разрезать плитку на минимально возможное количество кусочков.
Следуя этим правилам, Рисунок 2 демонстрирует пример разрезания плитки, показанной на Рисунке 1. Рисунки 3 и 4 не соответствуют правилам: на Рисунке 3 есть непрямоугольный кусочек, а на Рисунке 4 больше кусочков, чем на Рисунке 2.
Рисунок 2: Пример разрезания, соответствующий правилам
Рисунок 3: Пример разрезания, оставляющий непрямоугольный кусочек
Рисунок 4: Пример разрезания, дающий больше кусочков, чем на Рисунке 2
Ваша задача — написать программу, которая вычисляет количество кусочков шоколада после разрезания в соответствии с правилами.
Входные данные
Входные данные состоят из последовательности наборов данных. Конец ввода обозначается строкой с двумя нулями, разделенными пробелом. Каждый набор данных имеет следующий формат:
h wr_{(1, 1)} ... r_{(1, w)}r_{(2, 1)} ... r_{(2, w)}...r_{(h, 1)} ... r_{(h, w)}
Целые числа h и w обозначают размеры шоколадной плитки в сегментах. Вы можете предположить, что 2 ≤ h ≤ 100 и 2 ≤ w ≤ 100. Каждая из следующих h строк содержит w символов, каждый из которых либо ".", либо "#". Символ r_{(i, j)} указывает, есть ли сегмент шоколада в позиции (i, j):
".": Шоколада нет.
"#": Сегмент шоколада присутствует.
Вы можете быть уверены, что ни один набор данных не представляет собой несколько несвязанных плиток, как на Рисунке 5, или плитку с отверстием(ями), как на Рисунках 6 и 7. Также в каждом наборе данных есть хотя бы один символ "#".
Рисунок 5: Несвязанные шоколадные плитки
Рисунок 6: Шоколадная плитка с отверстием
Рисунок 7: Еще один пример шоколадной плитки с отверстием
Выходные данные
Для каждого набора данных выведите строку с целым числом, представляющим количество кусочков шоколада, полученных после разрезания в соответствии с правилами. Никакие другие символы не допускаются в выводе.