Find maximum sub-square matrix with all 1's

Find maximum sub-square matrix with all 1's



Implementation:


#include <stdio.h>
#include <stdlib.h>
#define R 6
#define C 5

/* findmin function to return the minimum value among a, b , c */
int findmin(int a,int b,int c)
{
 if(a<b && a<c)
  return a;
 else if(b<c)
  return b;
 else
  return c;
}

int main(void) {
 int a[R][C],O[R][C];
 int i,j,max,imax,jmax;
 
 /* Get the input 2-D array */
 for(i=0;i<R;i++)
 {
  for(j=0;j<C;j++)
  {
   scanf("%d",(*(a+i)+j));
  }
 }
 
 /* Copy the first row of input array to output array */
 for(j=0;j<C;j++)
  O[0][j]=a[0][j];
  
    /* copy the first column of input array to output array */
 for(i=0;i<R;i++)
  O[i][0]=a[i][0];
 
 /* Fill the remaining elements of the output array by adding one to the minimum among
 (i-1)th row (j)th column &&
 (i)th row (j-1)th column &&
 (i-1)th row (j-1)th column */
 
 for(i=1;i<R;i++)
 {
  for(j=1;j<C;j++)
  {
   if(a[i][j]==1)
    O[i][j]=(findmin(O[i-1][j],O[i][j-1],O[i-1][j-1]))+1;
   else
    O[i][j]=0;
  }
 }
 /*To print the matrix O[R][C]
 for(i=0;i<R;i++)
 {
  for(j=0;j<C;j++)
  {
   printf("%d ",O[i][j]);
  }
  printf("\n");
 }*/
 
 /* Assume that the first element is maximum element initially */
 max=O[0][0];
 imax=0;
 jmax=0;
 
 /* find the maximum value from the output array along with row index & column index */
 for(i=0;i<R;i++)
 {
  for(j=0;j<C;j++)
  {
   if(O[i][j] > max)
   {
    max=O[i][j];
    imax=i;
    jmax=j;
   }
  }
 }
 
 /* Print the result array in such a way that the array starts from maximum indices & 
 ends at difference of the maximum element of the array & indices */
 for(i=imax;i>imax-max;i--)
 {
  for(j=jmax;j>max-jmax;j--)
  {
   printf("%d",a[i][j]);
  }
  printf("\n");
 }
 return 0;
}


Input:

1 1 1 1
0 0 0 0 
1 1 1 1
1 1 1 1

Output:

1 1 1 1
1 1 1 1