Cod sursa(job #51156)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 10 aprilie 2007 13:02:44
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <stdio.h>
#include <string.h>
#define NMAX 202

int A[NMAX][NMAX], B[NMAX][NMAX], C[NMAX][NMAX];
int N, M, V[NMAX], T[NMAX];

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

int main()
{
        int i, j, k, uv, nv = 0, max1 = 0, max2 = 0, smax = 0;
        char c;

        freopen("bmatrix.in", "r", stdin);
        scanf("%d %d", &N, &M);

        for (i = 1; i <= N; i++)
            for (j = 1; j <= M; j++)
            {
               scanf(" %c", &c);
               A[i][j] = c-48;
               B[i][j] = B[i-1][j]+A[i][j];
               C[i][j] = C[i][j-1]+A[i][j];
            }

        for (i = 1; i <= N; i++)
            for (j = i; j <= N; j++)
            {
                max1 = 0; uv = 0;
                for (k = 1; k <= M; k++)
                    if (B[j][k]-B[i-1][k] == 0)
                       max1 = max(max1, uv+j-i+1), uv += (j-i+1);
                    else uv = 0;
                V[j] = max(V[j], max1);
            }

        for (i = N; i >= 1; i--)
            for (j = i; j >= 1; j--)
            {
                max1 = 0; uv = 0;
                for (k = 1; k <= M; k++)
                    if (B[i][k]-B[j-1][k] == 0)
                       max1 = max(max1, uv+i-j+1), uv += (i-j+1);
                    else uv = 0;
                T[j] = max(T[j], max1);
            }

        for (i = 1; i <= N; i++) V[i] = max(V[i], V[i-1]);
        for (i = N; i >= 1; i--) T[i] = max(T[i], T[i+1]);

        smax = 0;
        for (i = 1; i < N; i++)
            if (V[i] != 0 && T[i+1] != 0)
               smax = max(smax, V[i]+T[i+1]);
	for (i = 0; i < NMAX; i++) T[i] = V[i] = 0;

        for (i = 1; i <= M; i++)
            for (j = i; j <= M; j++)
            {
                max1 = 0; uv = 0;
                for (k = 1; k <= N; k++)
                    if (C[k][j]-C[k][i-1] == 0)
                       max1 = max(max1, uv+j-i+1), uv += (j-i+1);
                    else uv = 0;
                V[j] = max(V[j], max1);
            }

            for (i = M; i >= 1; i--)
                for (j = i; j >= 1; j--)
                {
                    max1 = 0; uv = 0;
                    for (k = 1; k <= N; k++)
                        if (C[k][i]-C[k][j-1] == 0)
                           max1 = max(max1, uv+i-j+1), uv += (i-j+1);
                        else uv = 0;
                    T[j] = max(T[j], max1);
                }

        for (i = 1; i <= N; i++) V[i] = max(V[i], V[i-1]);
        for (i = N; i >= 1; i--) T[i] = max(T[i], T[i+1]);

        for (i = 1; i < N; i++)
            if (V[i] != 0 && T[i+1] != 0)
               smax = max(smax, V[i]+T[i+1]);

        freopen("bmatrix.out", "w", stdout);
        printf("%d\n", smax);

        return 0;
        
}