Maximum Star Square

You are given a grid of characters with n rows and m columns. Each character is either a star (*) or a dot (.). Your task is to compute the maximum side length of a square in the grid such that all its cells are stars.

The problem can be solved using dynamic programming. For each cell in the grid that contains a star, you can calculate the size of the largest square that ends at that cell using the recurrence:

\(dp[i][j] = \min(dp[i-1][j],\, dp[i][j-1],\, dp[i-1][j-1]) + 1\) if the cell \((i,j)\) contains a star, and 0 otherwise.

The answer to the problem is the maximum value in the DP table.

inputFormat

The first line contains two integers n and m (\(1 \leq n, m \leq 1000\)), representing the number of rows and columns of the grid.

Each of the next n lines contains a string of length m consisting of characters '*' or '.'.

outputFormat

Output a single integer: the maximum side length of a square that contains only stars.

3 4
*.*.
****
****

2