Задача №112701. Средиземье в опасности
Тёмные силы под руководством Саурона заполонили Средиземье, и только Арагорн, сын Араторна, наследник Исилдура и истинный правитель Гондора может найти силы противостоять Тёмному владыке Мордора. Впрочем, мы поможем ему в этом в другой раз, сейчас же давайте оценим, как далеко может зайти Тёмный Властелин.
Карта Средиземья представляет собой клетчатый прямоугольник из N строк по M клеток, каждая из которых может либо полностью принадлежать Саурону, либо полностью не принадлежать. Если в каком-либо квадрате размером 2 × 2 три клетки уже захвачены тёмными силами, то они способны захватить и четвёртую клетку.
Изначально полчищам Саурона уже подвластны некоторые клетки на карте Средиземья. Оцените, сколько клеток может оказаться под его контролем в худшем случае.
Первая строка входного файла содержит два целых числа N и M ( 1 ≤ N , M ≤ 40 ) — количество строк и столбцов на карте Средиземья. Следующие N строк по M символов описывают игровое поле в порядке следования сверху вниз, слева направо. Символ ‘ . ’ соответствует клетке карты, свободной от власти Саурона, а ‘ # ’ — клетке, захваченной Сауроном. Строки нумеруются от 1 до N , столбцы — от 1 до M .
В выходной файл выведите одно число — максимальное количество клеток, которые могут контролировать тёмные силы после всех завоеваний.
2 2 ## #.
4
3 4 #... #... ###.
9
3 5 ...## #.... #.#..
5