Помогите с заданием. Дан клетчатый прямоугольник из N строк по М клеток, каждая из которых или уже закрашена, или еще не закрашена. Если в каком-либо квадрате размером 2 х 2 три клетки уже закрашены, то можно закрасить и четвёртую клетку.
Оцените, сколько клеток могут в итоге оказаться закрашенными.
Формат входных данных:
Первая строка входных данных содержит два целых числа М и М (1 ≤N, M ≤ 500) количество строк и столбцов в прямоугольнике. Следующие N строк по М символов описывают клетки прямоугольника. Символ «.» соответствует незакрашенной клетке, а «#>> закрашенной клетке. Строки нумеруются от 1 до N, столбцы от 1 до М. Формат выходных данных:
Выведите одно число закрашенными. максимальное количество клеток, которые могут оказаться
Критерии оценивания
Каждый тест оценивается независимо. Решения, правильно работающие для ограничений 1N, M≤50, будут набирать не менее 60 баллов.
ввод:
2 2
##
#.
вывод:
4

ввод:
3 4
# . . .
# . . .
###.
вывод:
9

Для решения этой задачи, существует следующий алгоритм:

  1. Нужно пройтись по всем квадратам размером 2 х 2 в прямоугольнике;

  2. Если в каком-либо квадрате три клетки уже закрашены, нужно закрасить четвёртую клетку;

  3. Нужно повторить шаги 1-2 до тех пор, пока нельзя будет закрасить больше клеток.

Следуя этому алгоритму, можно определить максимальное количество закрашенных клеток в вашем прямоугольнике.