Largest Square Subgrid

You are given a grid with n rows and m columns. Each cell in the grid is represented by either a . character indicating a fertile cell or a # character indicating an infertile cell. Your task is to find the area of the largest square subgrid that consists entirely of fertile cells.

The problem can be modeled using dynamic programming. Let \(dp[i][j]\) represent the side length of the largest square subgrid ending at cell \((i, j)\). If the cell \((i, j)\) is fertile (i.e. .), then the recurrence is given by:

[ dp[i][j] = \min(dp[i-1][j],, dp[i][j-1],, dp[i-1][j-1]) + 1 ]

The area of the largest square is then \( (\max_{i,j} dp[i][j])^2 \). If there is no fertile cell or if the grid dimensions are 0, the answer should be 0.

inputFormat

The input is read from standard input and has the following format:

• The first line contains two integers n and m, representing the number of rows and columns respectively.
• The next n lines each contain a string of length m consisting only of the characters . and #.

If n or m is zero, then the grid is empty and the output should be 0.

outputFormat

Output a single integer to standard output which represents the area of the largest square subgrid consisting entirely of fertile cells.

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

4