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