Largest Square of 1's

Given an integer grid of size \( m \times n \) where each cell is either \(0\) or \(1\), you are required to determine the side length of the largest square sub-grid that contains only \(1\)'s. In other words, find the maximum integer \(k\) such that there exists a \(k \times k\) sub-grid completely filled with \(1\)'s.

The problem can be solved using a dynamic programming approach. For each cell \( (i,j) \) in the grid where the cell is \(1\), the maximum size of a square ending at that cell is given by:

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

with the boundary condition that if \(i = 0 \) or \(j = 0\), then \(dp[i][j] = 1\) if the cell value is \(1\), otherwise \(0\).

inputFormat

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

The next \(m\) lines each contain \(n\) space-separated integers (each either 0 or 1) describing the grid.

Input is read from standard input (stdin).

outputFormat

Output a single integer, which is the side length of the largest square sub-grid composed entirely of 1's, printed to standard output (stdout).

5 6
1 0 1 0 0 1
1 1 1 1 0 1
1 1 1 1 1 1
1 1 1 1 0 0
0 0 1 0 0 0

3