Brilliant example on dynamic programming

Imagine there is a square matrix with n x n cells. Each cell is either filled with a black pixel or a white pixel. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels;

white = 0 black = 1
1. construct a row and a col matrix to record the # of consecutive "1" from current node to left, and up, respectively.
e.g.:
Original (A):

             {{0,1,1,1,1,1},
               {0,1,1,1,1,1},
               {1,1,1,1,1,0},
               {1,1,0,1,1,1},
               {1,1,1,1,1,0},
               {0,1,1,1,1,0}};

we create a structure of array in that we store the value of contiguous one in row and column .

struct array{
int right ;
int down ;
};

struct array x[n][n];

output for the above array   .

for from this array we check the square for each block in the array .

code :->

#include<stdio.h>
#define n 6

struct array{
int right ;
int down ;
};

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

void preprosess(struct  array x[n][n],int arr[n][n]){

int i ,j;

for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      x[i][j].down=0;
      x[i][j].right=0;
      }
   }

   if(arr[0][0]==1){
    x[0][0].down=1;
      x[0][0].right=1;
   }

   for(i=0;i<n;i++){
    for(j=0;j<n;j++){

      if(i==0 && i!=j){
          if(arr[i][j]==1)
          {
              x[i][j].down=1;
              x[i][j].right=x[i][j-1].right+1;
          }

      }else{
      if(j==0&&i!=j){
         if(arr[i][j]==1)
          {
              x[i][j].down=x[i-1][j].down+1;
              x[i][j].right=1;
          }

      }else{

         if(arr[i][j]==1&&i!=0)
          {
              x[i][j].down=x[i-1][j].down+1;
              x[i][j].right=x[i][j-1].right+1;
          }
        }
      }

    }
   }

}

int issquar(struct array x[n][n],int i ,int j , int k){

    if(x[i][j-(k-1)].down>=k && x[i-(k-1)][j].right>=k)
        return 1 ;
return 0;
}


void checkborder(int arr[n][n]){

struct array x[n][n];
int i=0,j=0,len=-1;
struct array point ;
point.down=0;
point.right=0;
preprosess(x,arr);

for(i=0;i<n;i++){
        for(j=0;j<n;j++){
          printf("%d , %d     ",x[i][j].down,x[i][j].right);
          }
          printf("\n\n");
        }


for(i=0;i<n;i++){
        for(j=0;j<n;j++){

           if((x[i][j].down&&x[i][j].right)>=1){
           int min = (x[i][j].down,x[i][j].right);
           int k;
           for(k=min ; k>=1 ; k--){

               if(issquar(x,i,j,k)){
               if(k>len){
                len=k ;
                  point.down=i-(k-1);
                  point.right=j-(k-1);
               }
                break ;
               }
             }
           }

        }
    }



printf("\n\n\n\n");
printf("maximum square length %d \n",len);
printf("maximum square starts from \n i = %d  and j= %d \n",point.down , point.right);

}

void main(){

int arr[n][n]={{0,1,1,1,1,1},
               {0,1,1,1,1,1},
               {1,1,1,1,1,0},
               {1,1,0,1,1,1},
               {1,1,1,1,1,0},
               {0,1,1,1,1,0}};

checkborder(arr);
}