Maximum Square Subgrid

You are given a grid of size \(n \times m\) consisting of characters '0' and '1'. Your task is to find the side length of the largest square subgrid that contains only '1's. This problem can be efficiently solved using dynamic programming, where the state transition is given by:

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

if the cell at \((i,j)\) contains a '1'. Otherwise, \(dp[i][j] = 0\). The answer is the maximum \(dp[i][j]\) over all cells.

inputFormat

The input is read from standard input (stdin). The first line contains two space-separated integers \(n\) and \(m\) representing the number of rows and columns, respectively. The next \(n\) lines each contain a binary string of length \(m\) composed of the characters '0' and '1'.

outputFormat

Output a single integer to standard output (stdout) which is the side length of the largest square subgrid that contains only '1's.

5 5
10101
11111
11111
11111
10101

3