Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

```0 1 0 1 0 1
1 0 1 0 1 0
0 1 1 1 1 0
0 0 1 2 2 0
1 1 1 2 3 1```

the above given matrix is 5*6 ,

let n=5, be the rows of matrix .

m=6 ,be the columns of the matrix.

we will use dynamic programming :

take a dp(two dimensional array of size (n+1)*(m+1)) and fill the i=0 and j=0 row and colums with zeros.

if the matrix element is zero than fill  dp with zero,else if it is one take the min of

matrix[i][j-1], matrix[i-1][j], matrix[i-1][j-1]

than just find the maximun element in the whole 2D array.

dp filled in th above way is:

```0 0 0 0 0 0 0
0 0 1 0 1 0 1
0 1 0 1 0 1 0
0 0 1 1 1 1 0
0 0 0 1 2 2 0
0 1 1 1 2 3 1 ```

here is the c++ implementation:

```#include <iostream>
using namespace std;

int main() { int t; cin>>t;
while(t--)
{ int n,m;
cin>>n>>m;

int dp[n+1][m+1];   int maxele=0;
for(int i=0;i<n+1;i++)
{
for(int j=0;j<m+1;j++)
{
if(i==0 || j==0)
dp[i][j]=0;
else
{ cin>>dp[i][j];

if(dp[i][j]!=0)
{
int x= min(dp[i-1][j-1],dp[i-1][j]);
dp[i][j]=min(dp[i][j-1],x)+1;

maxele=max(dp[i][j],maxele);
}

}

}

}

cout<<maxele<<endl;

}
//code
return 0;
}```

here instead of difining a separate matrix we can directly take the input in dp 2D array.

darkmode