Maximum Square Without Zero

Given an n × m matrix that contains only 0s and 1s, find the side length of the largest square in the matrix which does not contain any 0. In other words, find the largest square submatrix consisting entirely of 1s.

The solution should compute the maximum possible side length L such that there exists an L × L square in the matrix where every element is 1.

The dynamic programming approach uses the relation:

\[ dp[i][j] = \begin{cases} 0 & \text{if } matrix[i][j] = 0, \ \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 & \text{if } matrix[i][j] = 1. \end{cases} \]

The answer is the maximum value in the dp table.

inputFormat

The first line contains two space-separated integers, n and m, representing the number of rows and columns of the matrix, respectively.

Each of the next n lines contains m space-separated integers (each either 0 or 1) representing a row of the matrix.

outputFormat

Output a single integer representing the side length of the largest square which does not contain any 0.

sample

1 1
0

0