Largest Empty Square in a Grid

You are given a grid with n rows and m columns. Each cell in the grid is either . representing an empty space or # representing an obstacle. Your task is to find the side length of the largest square sub-grid that consists entirely of empty cells.

One can formulate the recurrence relation using dynamic programming as follows:

\[ 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{if } grid[i][j] = '#' \end{cases} \]

The answer is the maximum value in the dp table.

inputFormat

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

1. The first line contains two integers n and m (the number of rows and columns respectively).
2. This is followed by n lines, each containing a string of length m which represents the grid. The characters in the string are either . (empty cell) or # (obstacle).

outputFormat

Output a single integer to stdout representing the side length of the largest square that can be formed using only empty cells.

4 5
.....
.#...
.....
...##

3