Cod sursa(job #357169)

Utilizator Addy.Adrian Draghici Addy. Data 18 octombrie 2009 12:07:07
Problema BMatrix Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.91 kb
#include <stdio.h>
#include <algorithm>
#define Nmax 203

using namespace std;

int S[Nmax][Nmax], MINi[Nmax][Nmax], MINj[Nmax][Nmax], A[Nmax][Nmax];
int MAX1[Nmax], MAX2[Nmax];
int n, m, i, j, L, C, sol1, sol2;
char x;

//stiu ca nu e optim, vreau doar sa vad cat ar lua :))

void construiesteL(int L) {
	memset(MAX1, 0, sizeof(MAX1)); memset(MAX2, 0, sizeof(MAX2));
	memset(MINi, 0, sizeof(MINi)); memset(MINj, 0, sizeof(MINj));
	for (i = 1; i <= m; i++)
		MINi[0][i] = MINj[0][i] = -1;
	for (i = 1; i <= n; i++)
		MINi[i][0] = MINj[i][0] = -1;
	
	for (i = 1; i <= L; i++)
		for (j = 1; j <= m; j++) {
			if (!A[i][j]) {
				MINi[i][j] = MINi[i-1][j] + 1, MINj[i][j] = MINj[i][j-1] + 1;
				S[i][j] = (MINi[i][j]+1) * (MINj[i][j]+1);
			}
			else {
				S[i][j] = 0;
				MINi[i][j] = -1, MINj[i][j] = -1;
			}
			if (S[i][j] > MAX1[j])
				MAX1[j] = S[i][j];
		}
	
	for (i = 1; i <= m; i++)
		MINi[L][i] = -1;
	
	for (i = L+1; i <= n; i++)
		for (j = 1; j <= m; j++) {
			if (!A[i][j]) {
				MINi[i][j] = MINi[i-1][j] + 1, MINj[i][j] = MINj[i][j-1] + 1;
				S[i][j] = (MINi[i][j]+1) * (MINj[i][j]+1);
			}
			else {
				S[i][j] = 0;
				MINi[i][j] = -1, MINj[i][j] = -1;
			}
			if (S[i][j] > MAX2[j])
				MAX2[j] = S[i][j];
		}
}

void construiesteC(int C) {
	memset(MAX1, 0, sizeof(MAX1)); memset(MAX2, 0, sizeof(MAX2));
	memset(MINi, 0, sizeof(MINi)); memset(MINj, 0, sizeof(MINj));
	for (i = 1; i <= m; i++)
		MINi[0][i] = MINj[0][i] = -1;
	for (i = 1; i <= n; i++)
		MINi[i][0] = MINj[i][0] = -1;
	
	for (j = 1; j <= C; j++)
		for (i = 1; i <= n; i++) {
			if (!A[i][j]) {
				MINi[i][j] = MINi[i-1][j] + 1, MINj[i][j] = MINj[i][j-1] + 1;
				S[i][j] = (MINi[i][j]+1) * (MINj[i][j]+1);
			}
			else {
				S[i][j] = 0;
				MINi[i][j] = -1, MINj[i][j] = -1;
			}
			if (S[i][j] > MAX1[i])
				MAX1[i] = S[i][j];
		}
	
	for (i = 1; i <= n; i++)
		MINj[i][C] = -1;
	
	for (j = C+1; j <= m; j++)
		for (i = 1; i <= n; i++) {
			if (!A[i][j]) {
				MINi[i][j] = MINi[i-1][j] + 1, MINj[i][j] = MINj[i][j-1] + 1;
				S[i][j] = (MINi[i][j]+1) * (MINj[i][j]+1);
			}
			else {
				S[i][j] = 0;
				MINi[i][j] = -1, MINj[i][j] = -1;
			}
			if (S[i][j] > MAX2[i])
				MAX2[i] = S[i][j];
		}
}

int main() {
	
	FILE *f = fopen("bmatrix.in", "r");
	FILE *g = fopen("bmatrix.out", "w");
	
	fscanf(f, "%d %d", &n, &m);
	
	for (i = 1; i <= n; i++) {
		fscanf(f, "\n");
		for (j = 1; j <= m; j++) {
			fscanf(f, "%c", &x);
			A[i][j] = x - 48;
		}
	}
	
	for (L = 1; L < n; L++) {
		construiesteL(L);
		sort(MAX1+1, MAX1+1+m);
		sort(MAX2+1, MAX2+1+m);
		if (MAX1[m] + MAX2[m] > sol1)
			sol1 = MAX1[m] + MAX2[m];
	}
	
	for (C = 1; C < m; C++) {
		construiesteC(C);
		sort(MAX1+1, MAX1+1+n);
		sort(MAX2+1, MAX2+1+n);
		if (MAX1[n] + MAX2[n] > sol2)
			sol2 = MAX1[n] + MAX2[n];
	}
	
	fprintf(g, "%d", sol1>sol2?sol1:sol2);
	
	fclose(f);
	fclose(g);
	
	return 0;
}