Largest Square Subgrid of O's

Given an n × m grid consisting of characters 'O' and 'X', your task is to find the side length of the largest square subgrid that is composed entirely of 'O' characters. A dynamic programming approach can be used to solve this problem. Define a DP matrix \(dp\) such that:

\(dp[i][j] = \min\big(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]\big) + 1\) if the cell at position \((i, j)\) is 'O', and 0 otherwise. The answer is the maximum value in \(dp\).

inputFormat

The first line of input contains two integers n and m, representing the dimensions of the grid. This is followed by n lines, each containing a string of m characters (either 'O' or 'X') representing the grid.

outputFormat

Output a single integer – the side length of the largest square subgrid that contains only the character 'O'.## sample

4 5
XXOXO
XOXOX
XXXOO
OOOOO

2