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

Разрез

Разрез

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Когда Фродо, Сэм, Мерри и Пиппин сидели в Зеленом Драконе и пили пиво, они решили сыграть в небольшую игру с бумагой и ручкой, чтобы решить кто покупает пиво в следующем раунде. Игра имеет следующий вд:

Имеется прямоугольная доска m × n, каждая клетка которой обозначена одной из букв W, I или N. Найдите наибольшее количество триомино, которое можно вырезать из доски таким образом, чтобы клетки W и N были на концах триомино, а I посередине (то есть можно было бы прочитать WIN в некотором порядке). Допустимыми триомино являются последовательности из трех клеток, расположенные в линию или уголком. Тот кто найдет наибольшее количество триомино, выигрывает и указывает на того кто идет за пивом. Вам следует найти наибольшее количество таких слов.

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

Состоит из нескольких тестов. Каждый тест содержит прямоугольную сетку m × n (1m, n30), содержащую буквы W, I и N. Тесты отделяются друг от друга пустой строкой.

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

Для каждого теста вывести в отдельной строке наибольшее количество триомино, которое можно вырезать из доски.

Пример

Входные данные #1
WIIW
NNNN
IINN
WWWI

NINWN
INIWI
WWWIW
NNNNN
IWINN
Выходные данные #1
5
5
Источник 2012 North America - Pacific Northwest Region Programming Contest, Ноябрь 3, Задача K