Largest Square of Free Space

Given a grid of dimensions \(N \times M\) consisting only of characters '#' and '.', your task is to determine the side length of the largest square of free space (cells represented by '.') in the grid. The problem can be solved with dynamic programming.

The algorithm works by maintaining a 2D DP table where \(dp[i][j]\) represents the side length of the largest square whose bottom-right corner is at cell \((i, j)\). The recurrence relation for the update is: \[ dp[i][j] = \begin{cases} \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 given via stdin in the following format:

N M
grid[0]
grid[1]
...
grid[N-1]

Here, N and M are integers representing the number of rows and columns of the grid respectively. Each of the following N lines contains a string of M characters, each of which is either '.' (free space) or '#' (obstacle).

outputFormat

Output to stdout a single integer representing the side length of the largest square that consists entirely of free spaces.

5 5
.....
..#..
.#...
.....
.....

3