#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define PLUS_INFTY 1000000000
#define MINUS_INFTY -1000000000

char **genmatrix ( int m, int n )
{
   char **M, prev;
   int i, j;

   M = (char **)malloc(m * sizeof(char *));
   for (i=0; i<m; ++i) {
      M[i] = (char *)malloc(n * sizeof(char));
      prev = (i == 0) ? 'W' : M[i-1][0];
      for (j=0; j<n; ++j) {
         if (rand() % 16) M[i][j] = (prev == 'W') ? 'B' : 'W';
         else M[i][j] = (rand() % 2) ? 'W' : 'B';
         prev = M[i][j];
         printf("%d ", (M[i][j] == 'W') ? 0 : 1);
      }
      printf("\n");
   }
   return M;
}

void prnblock ( char **M, int m, int n, int i, int j, int k, int l )
{
   int u, v;

   for (u=0; u<m; ++u) {
      printf("    ");
      for (v=0; v<n; ++v) {
         if ((u >= i) && (u < i+k) && (v >= j) && (v < j+l))
            printf("%c ", M[u][v]);
         else
            printf(". ");
      }
      printf("\n");
   }
}

int ischessboard ( char **M, int i, int j, int k, int l )
{
   int u, v;
   char prev;

   prev = (M[i][j] == 'W') ? 'B' : 'W';
   for (u=i; u<i+k; ++u) {
      for (v=j; v<j+l; ++v) {
         if (M[u][v] == prev) return 0;
         prev = M[u][v];
      }
      prev = M[u][j];
   }
   return 1;
}

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

void essquare ( char **M, int m, int n )
{
   int i, j, imax, jmax, L, l, lmax;

   lmax = MINUS_INFTY;
   for (i=0; i<m; ++i) {
      for (j=0; j<n; ++j) {
         L = min(m-i,n-j);
         for (l=L; l>=1; --l) {
            if (ischessboard(M,i,j,l,l)) break;
         }
         if (l >= lmax) {
            imax = i; jmax = j; lmax = l;
         }
      }
   }
   printf("\n+++ Exhaustive search: Square\n");
   prnblock(M,m,n,imax,jmax,lmax,lmax);
   printf("    Area = %d\n", lmax*lmax);
}

void esrectangle ( char **M, int m, int n )
{
   int i, j, imax, jmax, K, k, L, l, kmax, lmax, Amax;

   Amax = MINUS_INFTY;
   for (i=0; i<m; ++i) {
      for (j=0; j<n; ++j) {
         K = m-i; L = n-j;
         for (k=K; k>=1; --k) {
            for (l=L; l>=1; --l) {
               if (ischessboard(M,i,j,k,l)) break;
            }
            if (k*l > Amax) {
               imax = i; jmax = j;
               kmax = k; lmax = l;
               Amax = k*l;
            }
         }
      }
   }
   printf("\n+++ Exhaustive search: Rectangle\n");
   prnblock(M,m,n,imax,jmax,kmax,lmax);
   printf("    Area = %d\n", Amax);
}

void dpsquare ( char **M, int m, int n )
{
   int i, j, l1, l2, imax, jmax, lmax;
   int **L;

   L = (int **)malloc(m * sizeof(int *));
   for (i=0; i<m; ++i) L[i] = (int *)malloc(n * sizeof(int));
   for (j=0; j<n; ++j) L[m-1][j] = 1;
   for (i=0; i<m; ++i) L[i][n-1] = 1;
   imax = m-1; jmax = n-1; lmax = 1;
   for (i=m-2; i>=0; --i) {
      for (j=n-2; j>=0; --j) {
         if ((M[i][j] == M[i+1][j]) || (M[i][j] == M[i][j+1])) L[i][j] = 1;
         else {
            l1 = L[i+1][j];
            l2 = L[i][j+1];
            if (l1 < l2) L[i][j] = l1 + 1;
            else if (l1 > l2) L[i][j] = l2 + 1;
            else if (M[i+l1][j+l2] != M[i+l1][j+l2-1]) L[i][j] = l1 + 1;
            else L[i][j] = l1;
         }
         if (L[i][j] > lmax) {
            imax = i; jmax = j; lmax = L[i][j];
         }
      }
   }
   for (i=0; i<m; ++i) free(L[i]);
   free(L);
   printf("\n+++ Dynamic Programming: Square\n");
   prnblock(M,m,n,imax,jmax,lmax,lmax);
   printf("    Area = %d\n", lmax*lmax);
}

void dprectangle ( char **M, int m, int n )
{
   int i, j, k, l, imax, jmax, kmax, lmax, Amax;
   int **K, **L;

   /* K[i][j] stores the length of the longest sequence of alternating
      colors starting vertically from M[i][j].

      L[i][j] stores the length of the longest sequence of alternating
      colors starting horizontally from M[i][j]. */

   K = (int **)malloc(m * sizeof(int *));
   L = (int **)malloc(m * sizeof(int *));
   for (i=0; i<m; ++i) {
      K[i] = (int *)malloc(n * sizeof(int));
      L[i] = (int *)malloc(n * sizeof(int));
   }

   for (i=0; i<m; ++i) {
      L[i][n-1] = 1;
      for (j=n-2; j>=0; --j)
         L[i][j] = (M[i][j] == M[i][j+1]) ? 1 : L[i][j+1] + 1;
   }

   for (j=0; j<n; ++j) {
      K[m-1][j] = 1;
      for (i=m-2; i>=0; --i)
         K[i][j] = (M[i][j] == M[i+1][j]) ? 1 : K[i+1][j] + 1;
   }

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

         /* Setting T(i,j): The allowed values of k are 1,2,3,...,K[i][j].
            For any allowed value of k, the maximum allowed value of l is
            min[L(i,j),L(i+1,j),L(i+2,j),...,L(i+k-1,j)]. */

         l = PLUS_INFTY;
         for (k=1; k <= K[i][j]; ++k) {
            l = min(l,L[i+k-1][j]);
            if (k * l > Amax) {
               imax = i; jmax = j;
               kmax = k; lmax = l;
               Amax = k * l;
            }
         }
      }
   }

   for (i=0; i<m; ++i) { free(K[i]); free(L[i]); }
   free(K); free(L);
   printf("\n+++ Dynamic Programming: Rectangle\n");
   prnblock(M,m,n,imax,jmax,kmax,lmax);
   printf("    Area = %d\n", Amax);
}

int main ( int argc, char *argv[] )
{
   int m, n;
   char **F;

   srand((unsigned int)time(NULL));
   if (argc == 1) m = n = 20;
   else if (argc == 2) m = n = atoi(argv[1]);
   else { m = atoi(argv[1]); n = atoi(argv[2]); }
   printf("%d %d\n", m, n);

   F = genmatrix(m,n);

   essquare(F,m,n);

   esrectangle(F,m,n);

   dpsquare(F,m,n);

   dprectangle(F,m,n);

   exit(0);
}