Largest Square of Dots

Given a grid of size \(n \times m\) composed of characters '.' and '#' where '.' represents a free cell and '#' represents a blocked cell, your task is to find the area of the largest square consisting entirely of '.' characters.

The problem requires you to compute the largest square sub-matrix in which every cell is a dot. If no such square exists, output 0.

Input Format: The first line contains two integers \(n\) and \(m\) denoting the number of rows and columns respectively. The following \(n\) lines each contain a string of length \(m\) representing the grid.

Output Format: Print a single integer which is the area of the largest square of dots.

Recall the classic dynamic programming approach where you maintain a \(dp\) table with the recurrence:

\[ dp[i][j] = \begin{cases} 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{if } grid[i][j] = '.' \\ 0 & \text{otherwise} \end{cases} \]

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 of the grid. The following \(n\) lines each contain a string of length \(m\) consisting of '.' and '#' characters.

outputFormat

Output a single integer which is the area (i.e., side length squared) of the largest square which contains only '.' characters.

5 6
....#.
...##.
.##...
....#.
#.....

4