Maximum size square sub-matrix problem, given an input matrix filled with 0 and 1. find the largest square sub-matrix
with all 1s.

For example 1.

```1    0    1
1    0    1
1    1    1
1    1    0
1    1    0
```

The largest square sub-matrix with all 1s is
1 1
1 1

For example 2. Let see below input matrix

```0    1    0    0    1   1
1    0    0    1    0   0
0    1    1    1    1   1
0    1    1    1    1   1
1    1    1    1    1   1
0    0    1    1    1   1
```

The largest square sub-matrix with all 1s is

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

## Solution:  Dynamic programming for Maximum size square sub-matrix problem

Step 2:  Rest of the filling of auxiliary matrix will be as follows:

1. If any cell of original matrix is 0, copy this cell corresponding to auxiliary matrix  cell, as it is.
2. Else if any cell ( for ex. m[i][j] ) of original matrix is 1, then  find minimum of left cell m[i-1][j], top cell m[i][j-1], left top diagonal m[i-1][j-1] and +1.

if m[i][j] == 0 then c[i][j] = 0  ( where c is auxiliary matrix )

if m[i][j] == 1 then min(m[i-1][j], top cell m[i][j-1], left top diagonal m[i-1][j-1]) + 1

max size sub matrix with all 1s is largest matrix cell of auxiliary matrix.

Here is sample implementation in c , based on the above concept.

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

#define row 5
#define col 3

void processMatrix (int m[row][col])
{
int i;
int j;

// create an auxiliary matrix c
int **c = new int*[row];
for(i=0;i < row;i++)
c[i] = new int[col];

// copy the first row
for (i = 0; i < col; i++)
{
c[0][i] = m[0][i];
}
// copy the first column
for (i = 0; i < row; i++)
{
c[i][0] = m[i][0];
}

// for rest of the matrix
// check if m[i][j]==1
for (i = 1; i < row; i++)
{
for (j = 1; j < col; j++)
{
if (m[i][j] == 1)
{
c[i][j] = min (c[i - 1][j - 1], min (c[i][j - 1], c[i - 1][j])) + 1;
}
else
{
c[i][j] = 0;
}
}
}
// find the maximum size of sub matrix
int max = 0;
for (i = 0; i < row; i++)
{
for (j = 0; j < col; j++)
{
if (c[i][j] > max)
{
max = c[i][j];
}
}
}
/* print auxiliary matrix */
/*
for (i = 0; i < row; i++)
{
for (j = 0; j < col; j++)
{
cout<<c[i][j]<<" ";
}
cout<<endl;
}*/
cout<<"max size square sub-matrix is: "<<max;
cout<<endl;
}

int main ()
{
int m[row][col] = { {1, 0, 1},
{
1, 0, 1},
{
1, 1, 1},
{
1, 1, 0},
{
1, 1, 0}
};
processMatrix(m);
return 0;
}
```