Дан клетчатый прямоугольник из N строк по М клеток, каждая из которых или уже закрашена, или еще не закрашена. Если в каком-либо квадрате размером 2 × 2 три клетки уже закрашены, то можно закрасить и четвёртую клетку. Оцените, сколько клеток могут в итоге оказаться закрашенными. Формат входных данных Первая строка входных данных содержит два целых числа N и M (1 < N, M < 500) – количество строк и столбцов в прямоугольнике. Следующие N строк по М символов описывают клетки прямоугольника. Символ «

Для решения этой задачи нам необходимо пройтись по каждому квадрату размером 2×2 в прямоугольнике и проверить, сколько из этих квадратов имеют уже закрашенные 3 клетки. Если такие квадраты есть, то мы можем закрасить 4-ю клетку.

Шаги решения:
1. Считываем значения N и M – количество строк и столбцов прямоугольника.
2. Создаем двумерный массив размером N x M, в котором будем хранить состояние каждой клетки: 1 – клетка закрашена, 0 – клетка не закрашена.
3. Считываем состояние каждой клетки прямоугольника и заполняем массив.
4. Создаем переменную count и инициализируем ее нулем – она будет считать количество закрашенных клеток.
5. Проходимся по каждому квадрату размером 2×2 в прямоугольнике (используя два вложенных цикла со счетчиками i и j от 0 до N-2 и от 0 до M-2 соответственно).
6. Внутри каждого квадрата проверяем, сколько из 4-х клеток уже закрашены. Если в этом квадрате 3 клетки закрашены, то увеличиваем переменную count на 1.
7. Выводим значение count – количество закрашенных клеток.

Алгоритм имеет временную сложность O(N*M), где N и M – размеры прямоугольника.