Завдання з біології#149

Завдання з біології

1 секунда
512 мегабайтів
Середня

Степан, готуючись до олімпіади з програмування, пропустив багато уроків біології, і щоб виправити становище, взявся за непросте завдання. Це завдання полягає в аналізі зображень, отриманих за допомогою електронних мікроскопів.

Перед проведенням аналізу зображення проходять кілька стадій фільтрації. На першій стадії зображення переводиться в монохромне, тобто що має тільки два кольори: білий та чорний. Друга стадія є більш складною і полягає у видаленні шумів із зображення шляхом підбору фільтра. Але це виявилося непросто, оскільки для різних видів зображень потрібні різні фільтри. З метою підбору відповідного фільтра було вирішено перед другою стадією фільтрації проводити додаткові розрахунки.

Додаткові розрахунки полягають у знаходженні коефіцієнта зв'язності вихідного зображення. Коефіцієнт зв'язності — це число різних пар сусідніх пікселів. Зображення являє собою прямокутну таблицю пікселів розміру N \times M. Кожен піксель має або білий колір, або чорний. Два різних пікселя називаються сусідніми, якщо виконуються наступні умови:

  1. Обидва пікселя мають білий колір.

  2. Обидва пікселя знаходяться або в одному і тому ж стовпці або в одному і тому ж рядку.

  3. Всі пікселі, що перебувають або в рядку, або в стовпці між зазначеними пікселями, є білими.

Малюнок №1: N = 5 і M = 6, приклад сусідніх символів для пікселя .

Для наведеного вище прикладу всі зафарбовані пікселі є сусідніми для пікселя, позначеного зірочкою. Дві пари сусідніх пікселів, які можуть бути отримані одна з іншої за допомогою перестановки елементів, не вважаються різними. Тобто пара сусідніх пікселів \{(2; 4), (2; 6)\} і пара \{(2; 6), (2; 4)\} не рахуються різними.

Степану потрібно написати програму, яка по заданому опису зображення розраховує коефіцієнт зв'язності даного зображення. Допоможіть йому.

Вхідні дані

Перший рядок вхідного файлу містить два цілих числа і (1 \leq N, M \leq 200). Далі йдуть рядків по символів в кожній, що описують задане монохромне зображення. Символ '.' (ASCII 46) — позначає білий символ, а '#' (ASCII 35) — чорний.

Вихідні дані

Одне ціле число — коефіцієнт зв'язності вихідного монохромного зображення.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading