eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сорняк

Сорняк

Андрей посетил свой сад в последний раз много лет назад. Сегодняшние налоги на недвижимость настолько высоки, что Андрей решил продать свой сад. Земля долгое время не культивировалась, и теперь на ней, вероятно, много сорняков. Перед продажей Андрей хочет удалить все со своей земли. Теперь он хочет оценить объем работы.

Сад имеет прямоугольную форму и разбит на n * m равных квадратов. Память Андрея феноменальна. Он помнит, какие квадраты были заняты сорняками. Для простоты Андрей считает, что каждый квадрат либо полностью занят сорняком, либо полностью свободен от него. Эндрю нравится ботаника, и он знает, что если какой-нибудь квадрат свободен от сорняков, но по крайней мере два из его смежных квадратов заняты сорняками (два квадрата смежные, если они имеют общую сторону), то этот квадрат также будет занят сорняком в ближайшее время. Андрей уверен, что в последние годы сорняки занимали почти каждый квадрат. Помогите Андрею оценить, сколько квадратов занято сорняками.

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

Первая строка содержит целые числа n и m (1n, m1000). Каждая из следующих n строк содержит m символов. Символ X означает что соответствующая клетка оккупирована сорняком. Символ точки ( . ) означает пустую клетку.

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
3 3
X..
.X.
.X.
Выходные данные #1
6
Входные данные #2
3 4
X..X
.X..
.X..
Выходные данные #2
12
Источник 2007 Петрозаводск, Saratov for Karelia with love, Январь 28, Задача H