eolymp
Задачі

Шоколад

Шоколад

У Марічки та Зеника є прямокутна плитка смачного українського шоколаду. Плитка складається з однакових квадратиків, кожен з яких може бути або чорним, або білим.

Марічка проведе довільну (можливо, нульову) кількість повних горизонтальних (зліва направо) розрізів плитки, тоді як Зеник - довільну (можливо, нульову) кількість повних вертикальних (зверху вниз) розрізів. Зауважте, що розрізи можна проводити тільки між квадратиками плитки, а також що Зеник і Марічка можуть зробити різну кількість розрізів. Після проведення всіх розрізів плитка розпадеться на певну кількість прямокутних шматків, які наші герої певним чином розділять між собою.

Оскільки Зеник дуже любить чорний шоколад, він хоче, щоб після всіх розрізів кількість цілих шматків, які складаються виключно з чорних квадратиків, була якомога більшою. Марічка хоче цю саму кількість зробити якомога меншою. Зауважте, що героїв не цікавить, якого саме розміру будуть шматочки: головне - їхня кількість.

Щоб усе було чесно, Андрій окремо та незалежно запитає Марічку та Зеника, в яких саме місцях потрібно провести розрізи, а потім сам замість них проведе ці розрізи.

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

Вхідні дані

Перший рядок містить два цілих числа n і m (2n1000, 2m1000): висоту та ширину плитки відповідно. Далі йдуть n рядків по m символів в кожному, які позначають тип відповідного одиничного квадратика шоколадки. Символ B позначає чорний квадратик, а символ W білий.

Вихідні дані

Виведіть кількість шматків, які складатимуться виключно з квадратиків чорного шоколаду.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 4
BWBB
BBBW
BBBW
Вихідні дані #1
2
Джерело 2015 XXVIII Всеукраїнська олімпіада з інформатики