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

Острова

Острова

Ліміт часу 2 секунди
Ліміт використання пам'яті 128 MiB

Вы исследуете карту далекой планеты, используя спутник.

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

Остров представляет собой набор связанных наземных ячеек. Две ячейки считаются связанными, если они имеют общее ребро.

По заданному изображению определите максимально возможное количество островов в нем, которое согласуется с данной информацией.

Вхідні дані

Первая строка содержит два целых числа n и m (1n, m40).

Каждая из следующих n строк содержит m символов, описывающих изображение со спутника. Ячейки земли обозначаются символом L, ячейки воды - символом W, ячейки облаков - символом C.

Вихідні дані

Выведите одно целое число - максимально возможное количество островов, которое может присутствовать на заданной сетке.

Приклад

Вхідні дані #1
5 4
LLWL
CCCC
CCCC
CCCC
LWLL
Вихідні дані #1
8
Джерело 2016 ACM North America - Pacific Northwest, Дивизион 2, Задача T