Largest Square Subgrid of 1's

Given a grid of characters consisting of '0's and '1's, your task is to determine the side length of the largest square subgrid that contains only '1's. The subgrid must be contiguous and aligned with the original grid. Formally, you are given a grid with R rows and C columns; a cell in the grid is identified by its row and column indices. A square subgrid of side length L is valid if and only if all of its L × L entries are '1'.

The problem requires you to implement an efficient dynamic programming solution with a time complexity of O(R * C), which is suitable for grids of moderate size.

The mathematical formulation is as follows:

Let \(dp[i][j]\) denote the side length of the largest square subgrid with its bottom-right corner at \((i, j)\). Then, if \(grid[i][j] = 1\), we have:

[ dp[i][j] = \min{ dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1] } + 1 ]

Otherwise, \(dp[i][j] = 0\). The final answer is the maximum value found in the dp table.

inputFormat

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

R C
row1
row2
...
rowR

The first line contains two integers R and C, which indicate the number of rows and columns in the grid. Each of the following R lines contains a string of length C consisting of characters '0' and '1'.

outputFormat

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

## sample

4 5
01101
11111
11111
01111

3