Largest Square Submatrix

Given a binary matrix with m rows and n columns, find the side length of the largest square submatrix that consists entirely of 1s.

You can use dynamic programming to solve the problem. Let \(dp[i][j]\) denote the side length of the largest square whose bottom-right corner is at cell \((i,j)\). The recurrence is defined as:

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

where the boundaries (i.e. when \(i = 0\) or \(j = 0\)) are initialized as the value of the matrix itself. Your task is to implement a solution that reads the matrix from standard input and outputs, to standard output, the side length of the largest square submatrix of 1s.

inputFormat

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

• The first line contains two integers m and n, where m is the number of rows and n is the number of columns in the matrix.
• The next m lines each contain n integers (either 0 or 1) separated by spaces, representing the rows of the matrix.

outputFormat

Output to the standard output a single integer — the side length of the largest square submatrix consisting entirely of 1s.

4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

2