590. Determine the size of the largest square submatrix consisting of only 1's in a binary matrix
0
Medium
Given a binary matrix with dimensions M × N, determine the size of the largest square submatrix consisting of only 1's.
For example, in the following matrix:
0 0 1 0 1 1
0 1 1 1 0 0
0 0 1 1 1 1
1 1 0 1 1 1
1 1 1 1 1 1
1 1 0 1 1 1
1 0 1 1 1 1
1 1 1 0 1 1
The largest square submatrix of 0 1 1 1 0 0
0 0 1 1 1 1
1 1 0 1 1 1
1 1 1 1 1 1
1 1 0 1 1 1
1 0 1 1 1 1
1 1 1 0 1 1
1's has a size of 3.Input Format
The input consists of two integers, M and N, representing the number of rows and columns of a binary matrix.
This is followed by M*N integers representing the elements of the binary matrix.
This is followed by M*N integers representing the elements of the binary matrix.
Output Format
The output is an integer representing the size of the largest square submatrix consisting of only
1's and with a size of 1.Example
Input
10 10
1 1 1 1 1 0 0 1 1 1
0 1 1 1 1 1 0 1 0 1
0 0 1 0 1 1 1 0 0 1
1 0 1 1 1 0 1 1 0 1
0 0 0 1 0 0 0 1 0 1
1 0 1 1 1 0 0 1 1 0
0 0 0 0 1 0 0 1 0 1
0 1 1 1 1 1 1 1 0 0
1 1 1 1 1 0 0 1 1 1
0 0 1 0 0 1 1 0 0 1
Output
2
Constraints
0<=M,N<=50
0<=mat[i][j]<=1
0<=mat[i][j]<=1
Loading...
View Submissions
Console