Maximizing Non-Adjacent Flower Planting

You are given an M×N garden represented as a grid. Each cell in the grid is either . (an empty cell where a flower can be planted) or # (an obstacle where nothing can be planted). Your task is to plant as many flowers as possible such that no two flowers are adjacent. Two cells are considered adjacent if they share a common side or touch diagonally; in other words, for any planted flower at cell (i, j), no flower can be planted in any of the 8 neighboring cells. Mathematically, if a flower is planted at cell (i, j), then for every cell (k, l) with

$$|i - k| \le 1 \quad \text{and} \quad |j - l| \le 1,$$

there must be no other flower planted (except at (i, j) itself). The garden is processed in a greedy manner from the top-left cell to the bottom-right cell. Determine the maximum number of flowers that can be planted under these conditions.

inputFormat

The first line contains two integers M and N separated by a space, representing the number of rows and columns of the garden respectively. The next M lines each contain a string of length N consisting of characters . and # representing the garden grid.

outputFormat

Output a single integer which is the maximum number of flowers that can be planted following the given constraints.

3 3
.#.
#.#
.#.

4