Maximum Square Sub-matrix of Ones

You are given a binary matrix of size \( n \times m \) containing only 0s and 1s. Your task is to find the side length of the largest square sub-matrix that contains only 1s.

More formally, given a matrix \( A \) with entries \( a_{ij} \) where \( a_{ij} \in \{0,1\} \), you need to compute the maximum integer \( k \) such that there exists a submatrix of size \( k \times k \) with all entries equal to 1. The dynamic programming recurrence used to solve this problem is given by:

[ \text{dp}[i][j] = \begin{cases} 1 & \text{if } i=0 \text{ or } j=0 \text{ and } a_{ij}=1, \ \min{\text{dp}[i-1][j],,\text{dp}[i][j-1],,\text{dp}[i-1][j-1]} + 1 & \text{if } a_{ij}=1 \text{ and } i,j > 0, \ 0 & \text{if } a_{ij}=0. \end{cases} ]

The answer is the maximum value in the \(\text{dp}\) table.

inputFormat

The first line contains two integers \( n \) and \( m \) separated by a space, indicating the number of rows and columns of the matrix, respectively. The following \( n \) lines each contain \( m \) space-separated integers (each either 0 or 1) representing the matrix.

outputFormat

Output a single integer, which is the side length of the largest square sub-matrix that contains only 1s.

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

3