Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Анализ изображения

 Недавно в НИИ вычислительной биологии появилась непростая задача. Эта задача заключается в анализе изображений, полученных с помощью электронных микроскопов.

Перед проведением анализа изображения проходят несколько стадий фильтрации. На первой стадии изображение переводится в монохромное, т.е. имеющее только два цвета: белый и черный. Вторая стадия является более сложной  и заключается в удалении шумов из изображения путем подбора фильтра. Но это оказалось непросто, так как для разных видов изображений нужны разные фильтры. С  целью подбора подходящего фильтра было решено перед второй стадией фильтрации проводить дополнительные расчеты.

Дополнительные расчеты заключаются в нахождении коэффициента связности исходного изображения. Коэффициент связности – это число различных пар соседних пикселей.

Изображение представляет собой прямоугольную таблицу пикселей размера NxM. Каждый пиксель имеет либо белый цвет, либо черный. Два различных пикселя называются соседними, если выполняются следующие условия:

1. Оба пикселя имеют белый цвет.

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

Все пиксели,  находящиеся либо в строке, либо в столбце между указанными пикселями, являются белыми. 


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

Вам как младшему научному сотруднику НИИ было поручено написать программу, которая по заданному описанию изображения рассчитывает коэффициент связности данного изображения. 

Входные данные:

 Первая строка входного файла содержит два целых числа N и M (1 ≤ N, M ≤ 200).

Далее следуют N строк по M символов в каждой, описывающих исходное  монохромное изображение. Символ "." (ASCII 46) – обозначает белый символ, а "#" (ASCII 35) – черный. 

Выходные данные:

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


Примеры:
input.txt output.txt
1 2 3
...
.#.
5
2 3 4
...#
.#..
...#
13

Сложность задачи: 50%



Проверку могут осуществлять только зарегистрированные пользователи!


Показать обсуждение


На сайте гостей 18, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]