Counting Square Subgrids Without Obstacles

You are given a 2D grid representing a garden, where each cell is either free (denoted by '.') or contains an obstacle (denoted by '#'). Your task is to count the total number of square subgrids (contiguous square areas) that do not contain any obstacles.

A useful dynamic programming approach involves defining a dp-array where for each cell \(dp[i][j]\) represents the side length of the largest square subgrid ending at cell \((i, j)\) that does not contain any obstacles. The recurrence relation for this method is given by:

[ dp[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = '#' \ 1, & \text{if } i = 0 \text{ or } j = 0 \text{ and } grid[i][j] = '.' \ \min(dp[i-1][j],; dp[i][j-1],; dp[i-1][j-1]) + 1, & \text{otherwise} \end{cases} ]

The total count is the sum of all \(dp[i][j]\) for every cell in the grid.

inputFormat

The first line of input contains two space-separated integers \(n\) and \(m\), where \(n\) is the number of rows and \(m\) is the number of columns in the garden grid. This is followed by \(n\) lines, each containing a string of length \(m\) that represents a row of the garden. Each character is either '.' (free cell) or '#' (obstacle).

outputFormat

Output a single integer indicating the total number of square subgrids that do not contain any obstacles.

3 4
....
..#.
....

13