Cod sursa(job #22848)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 27 februarie 2007 17:54:24
Problema BMatrix Scor 48
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.78 kb
#include <stdio.h>
#include <string.h>
#define NMAX 222
#define max(a, b) ((a) > (b) ? (a):(b))

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

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

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

        for (i = 1; i <= N; i++)
	{
            gets(c); 
	    for (j = 1; j <= M; j++)
            {
               A[i][j] = c[j]-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]);

        memset(V, 0, sizeof(V));
        memset(T, 0, sizeof(T));

        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;
        
}