Cod sursa(job #357126)

Utilizator Addy.Adrian Draghici Addy. Data 18 octombrie 2009 00:32:54
Problema BMatrix Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 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, sol;
char x;

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

void construieste(int L) {
	for (i = 1; i <= m; i++) {
		MAX1[i] = MAX2[i] = 0;
		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];
		}
}

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++) {
		construieste(L);
		sort(MAX1+1, MAX1+1+m);
		sort(MAX2+1, MAX2+1+m);
		if (MAX1[m] + MAX2[m] > sol)
			sol = MAX1[m] + MAX2[m];
	}
	
	fprintf(g, "%d", sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}