Просто порахуйте фігури
Перегляд у форматі PDFРозглянемо прямокутну таблицю з ~N~ рядків, ~M~ стовпчиків. Кожна клітинка таблиці є або пустою (позначається як '.') або заповненою (позначаєтсья як '*'). Сусідні заповнені клітинки утворюють фігури. Детальніше:
клітини вважаються сусідніми, якщо вони мають спільне ребро;
заповнені клітинки належать до спільної фігури, якщо існує послідовність заповнених клітинок, яка починається в одній із заданих клітинок і закінчується в іншій заданій, і кожна наступна клітинка є сусідньою з попередньою.
Ваша задача — написати програму, яка визначає загальну кількість фігур. В цій задачі слід рахувати просто кількість фігур, ігноруючи питання, чи вони різні, чи однакові (однакові теж рахуються стільки разів, скільки їх є).
Вхідні дані
Ваша програма має прочитати кількість рядків ~N~ (~1≤N≤1234~), кількість стовпчиків ~M~ (~1≤M≤1234~) та ~N~ рядків, кожен з яких містить рівно ~M~ символів '*' та/або '.'.
Результат
Ваша програма повинна записати єдине ціле число — загальну кількість фігур.
Приклад
Вхідні дані
7 8
****.**.
****.**.
.....**.
.*.*.**.
.*.*...*
*.*.****
*.*.*.*.
Відповідь
7
Примітка
Ось копія вхідних даних, у якій фігури позначені різними цифрами, а клітинки в межах кожної фігури — однаковими між собою:
7 8
1111.22.
1111.22.
.....22.
.6.5.22.
.6.5...3
7.4.3333
7.4.3.3.
Коментарі