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

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

Maximum size square sub-matrix problem

    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;
}



Related Contents to follow