Пекарня 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: Інший приклад шоколадної плитки з отвором
Вихідні дані
Для кожного набору даних виведіть рядок, що містить ціле число, яке представляє кількість шматків шоколаду, отриманих після розрізання відповідно до правил. Інші символи у виході не допускаються.