Cod sursa(job #501005)

Utilizator andra23Laura Draghici andra23 Data 14 noiembrie 2010 00:28:34
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include<fstream>
#define maxn 205

using namespace std;

int a[maxn][maxn], b[maxn][maxn], m, n;
int v[5][maxn];
ofstream g("bmatrix.out");

void rotateRight(int a[][maxn], int b[][maxn]) {
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            b[j][m-i+1] = a[i][j];  
    int aux = m;
    m = n;
    n = aux;   
}

void findMax(int a[][maxn], int v[]){
    int i, j;
    int e[maxn][maxn];
    for (i = 1; i <= n; i++)
        e[0][i] = 0;
    v[0] = 0;
    for (j = 1; j <= n; j++)
        for (i = 1; i <= m; i++)
            if (a[i][j] == 1)
                e[i][j] = 0;
            else
                e[i][j] = e[i-1][j]+1;
    
    int s[1000], vf, h, l, area;
    for (i = 1; i <= m; i++) {
        v[i] = v[i-1];
        vf = 1;
        s[vf] = 1;
        for (j = 2; j <= n; j++) {
            h = e[i][j];
            l = s[vf];
            while (vf > 0 && e[i][s[vf]] > h) {
                area = e[i][s[vf]]*(l - s[vf-1]);
                if (area > v[i])
                    v[i] = area;
                vf--;    
            }
            vf++;
            s[vf] = j;    
        }
        l = s[vf];
        while (vf > 0){
            area = e[i][s[vf]]*(l - s[vf-1]);
            if (area > v[i])
                v[i] = area;
            vf--;        
        }
    }
}

int main(){
    ifstream f("bmatrix.in");
    
    f >> m >> n;
    int i, j, k;
    char s[maxn];
    for (i = 1; i <= m; i++) {
        f >> s;
        for (j = 0; j < n; j++) 
            a[i][j+1] = s[j] - '0';     
    }
    
    for (i = 1; i <= 4; i++) {
        findMax(a, v[i]);  
        rotateRight(a, b); 
        for (j = 1; j <= m; j++)
            for (k = 1; k <= n; k++)
                a[j][k] = b[j][k]; 
    }
    
    int max = 0;
    int lg[2];
    lg[1] = m;
    lg[2] = n;
    for (k = 1; k <= 2; k++) {
        for (i = 0; i <= lg[k]; i++) {
            if (v[k][i] + v[k+2][lg[k]-i] > max) {
                max = v[k][i] + v[k+2][lg[k]-i]; 
            }
        }    
    }
    
    g << max << '\n';
       
    return 0;
}