#### Miscellaneous

Problem
Given a matrix of 0s & 1s, find the maximum size square submatrix with all values as 1.
Consider the following matrix with 6 rows & 5 columns :-
0    1    0    0    1
1    0    0    1    0
0    1    1    1    1
0    1    1    1    0
1    1    1    1    1
0    0    0    0    0
Maximum size square sub-matrix is :-
1    1    1
1    1    1
1    1    1

Solution
Suppose the input matrix is mat [ m ][ n ]. We will maintain an auxilliary matrix aux [ m ][ n ] where each entry of aux is given by aux [ i ][ j ] = min ( aux [ i ][ j – 1 ] , aux [ i – 1 ][ j ] , aux [ i – 1 ][ j – 1 ] ) + 1 if mat [ i ][ j ] == 1 else aux [ i ][ j ] = 0 . Then we find the maximum entry in the aux matrix ( suppose it is k ) and backtrace from there to find the maximum square submatrix of size k by moving k cells upwards and leftwards.
See the implementation below.

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

int min(int a, int b) {
return ((a < b) ? a : b);
}

// print the maximum size square submatrix
// Logic :- Construct an auxilliary matrix 'aux' where each entry
// (i,j) is given by min[aux(i,j-1),aux(i-1,j),aux(i-1,j-1)] + 1 if mat(i,j) is 1.
// Find the max entry, suppose it is k
// then, max square submatrix is of size k and it can be traced
// by moving k cells upwards and leftwards
void printMaxSquareSubMat(bool mat,int row,int col) {
int i,j;
int aux[row][col]; //auxiliary matrix
int aux_max; // max value in auxilliary matrix
int x, y; // indices of the max value in auxilliary matrix

// initialize 1st column of aux
for (i = 0; i < row; i++)
aux[i] = mat[i];
// initialize 1st row of aux
for (j = 0; j < col; j++)
aux[j] = mat[j];

// compute other entries of auxilliary matrix
for (i = 1; i < row; i++) {
for (j = 1; j < col; j++) {
if (mat[i][j] == 1)
aux[i][j] = min(aux[i][j-1], min(aux[i-1][j], aux[i-1][j-1])) + 1;
else
aux[i][j] = 0;
}
}

// find the max value and its index in the
// auxilliary matrix
aux_max = aux; x = 0; y = 0;
for (i=0;i<row;i++) {
for (j=0;j<col;j++) {
if (aux_max < aux[i][j]) {
aux_max = aux[i][j];
x = i;
y = j;
}
}
}

// print the max size sq. submatrix
cout<<"\nMaximum size sub-matrix is:- \n";
for(i=x;i>(x-aux_max);i--) {
for(j=y;j>(y-aux_max);j--) {
cout<<mat[i][j]<<" ";
}
cout<<endl;
}
}

// main
int main() {
bool mat = {{0, 1, 0, 0, 1},
{1, 0, 0, 1, 0},
{0, 1, 1, 1, 1},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0}};
printMaxSquareSubMat(mat,6,5);
cout<<endl;
return 0;
}```