Cod sursa(job #13870)

Utilizator love_for_uSpancioc Riana love_for_u Data 7 februarie 2007 17:40:37
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.59 kb

#include <stdio.h>
#include <string.h>
#define MAX(a,b) ( (a) < (b) ? (b) : (a) )
#define MIN(a,b) ( (a) > (b) ? (b) : (a) )
#define NMAX 256

struct per { int val, poz; } A[NMAX], B[NMAX];

char Mat[NMAX][NMAX];
int Z[NMAX][NMAX], L1[NMAX], L2[NMAX], C1[NMAX], C2[NMAX];

int H[NMAX], Nr[NMAX], T[NMAX];
int C[NMAX], Viz[NMAX];
int N, M, i, j, k;
int rx, ry, nod;
int Amax;
int MaxA, Arie;

void sort(per A[], int L)
{
     int i, max = -1;

     memset(C, 0, sizeof(C));

     for (i = 1; i <= L; i++)
     {
          C[A[i].val] ++;

          max = MAX(max, A[i].val);
     }

     for (i = 1; i <= max + 1; i++) C[i] += C[i-1];

     for (i = L; i >= 0; i--) B[C[A[i].val]--] = A[i];
}


int rep(int x)
{
    return T[x] = ( T[x] == x ? x : rep(T[x]) );
}

void uneste(int rx, int ry)
{
     if (H[rx] > H[ry]) T[ry] = rx, Nr[rx] += Nr[ry];
     else
     if (H[rx] < H[ry]) T[rx] = ry, Nr[ry] += Nr[rx];
     else
     T[rx] = ry, H[ry]++, Nr[ry] += Nr[rx];
}

void unified(int nod1, int nod2)
{
     rx = rep(nod1);
     ry = rep(nod2);

     if (rx != ry)
     {
          Arie += Nr[ry];
          uneste(rx, ry);
     }
}

int solve(per A[], int L)
{
     int i;

     memset(Viz, 0, sizeof(Viz));
     memset(H, 0, sizeof(Viz));

     for (i = 1; i <= L; i++) A[i].poz = i, T[i] = i, Nr[i] = 1;

     sort(A, L);

     MaxA = 0;

     for (i = L; i >= 1; i--)
     {
          if (B[i].val == 0) break;

          nod = B[i].poz, Viz[nod] = 1, Arie = 1;

          if (Viz[nod + 1] == 1) unified(nod, nod + 1);

          if (Viz[nod - 1] == 1) unified(nod, nod - 1);

          Arie *= B[i].val;

          MaxA = MAX(MaxA, Arie);
     }

     return MaxA;
}

int main()
{
     freopen("bmatrix.in", "r", stdin);
     freopen("bmatrix.out", "w", stdout);

     scanf("%d %d\n", &N, &M);

     for (i = 1; i <= N; i++) gets(Mat[i]+1);

     // pt linii

     memset(Z, 0, sizeof(Z));

     for (i = N; i > 0; i--)
         for (j = 1; j <= M; j++)
             if (Mat[i][j] == '0') Z[i][j] = Z[i+1][j] + 1;

     for (i = 1; i <= N; i++)
     {
          for (j = 1; j <= M; j++) A[j].val = Z[i][j];

          L1[i] = solve(A, M);
     }

     memset(Z, 0, sizeof(Z));

     for (i = 1; i <= N; i++)
         for (j = 1; j <= M; j++)
             if (Mat[i][j] == '0') Z[i][j] = Z[i-1][j] + 1;

     for (i = 1; i <= N; i++)
     {
          for (j = 1; j <= M; j++) A[j].val = Z[i][j];

          L2[i] = solve(A, M);
     }

     //pt coloane

     memset(Z, 0, sizeof(Z));

     for (j = M; j >= 1; j--)
         for (i = 1; i <= N; i++)
             if (Mat[i][j] == '0') Z[i][j] = Z[i][j + 1] + 1;

     for (j = 1; j <= M; j++)
     {
          for (i = 1; i <= N; i++) A[i].val = Z[i][j];

          C1[j] = solve(A, N);
     }

     memset(Z, 0, sizeof(Z));

     for (j = 1; j <= M; j++)
         for (i = 1; i <= N; i++)
             if (Mat[i][j] == '0') Z[i][j] = Z[i][j - 1] + 1;

     for (j = 1; j <= M; j++)
     {
          for (i = 1; i <= N; i++) A[i].val = Z[i][j];

          C2[j] = solve(A, N);
     }

     //

     for (i = N; i >= 1; i--) L1[i] = MAX(L1[i+1], L1[i]);

     for (i = 1; i <= N; i++) L2[i] = MAX(L2[i-1], L2[i]);

     for (i = M; i >= 1; i--) C1[i] = MAX(C1[i+1], C1[i]);

     for (i = 1; i <= M; i++) C2[i] = MAX(C2[i-1], C2[i]);

     for (i = 1; i <= N + 1; i++)
         Amax = MAX(Amax, L1[i] + L2[i-1]);

     for (i = 1; i <= M + 1; i++)
         Amax = MAX(Amax, C1[i] + C2[i-1]);


     printf("%d\n", Amax);

     return 0;
}