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