Просто порахуйте фігури

Перегляд у форматі PDF

Надіслати розв'язок

Бали: 3,00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Suggester:
Problem type

Розглянемо прямокутну таблицю з ~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.

Коментарі

Please read the guidelines before commenting.


Ще немає коментарів.