Pagini recente » Cod sursa (job #2860463) | Cod sursa (job #553155) | Cod sursa (job #2128584) | Cod sursa (job #1481126) | Cod sursa (job #457307)
Cod sursa(job #457307)
#include <iostream>
using namespace std;
#define maxn 210
#define inf 999999999
//M linii si N coloane
int M, N;
char A[maxn][maxn];
int sus[maxn][maxn], jos[maxn][maxn];
int linsus[maxn], linjos[maxn];
int st[maxn][maxn], dr[maxn][maxn];
int colst[maxn], coldr[maxn];
int main() {
FILE *f1=fopen("bmatrix.in", "r"), *f2=fopen("bmatrix.out", "w");
int i, j, p, q;
fscanf(f1, "%d %d\n", &M, &N);
for(i=1; i<=M; i++) {
fscanf(f1, "%s\n", A[i] + 1);
}
for(i=1; i<=M; i++) {
for(j=1; j<=N; j++) {
if(A[i][j] == '0') sus[i][j] = sus[i-1][j] + 1;
}
}
for(i=M; i>=1; i--) {
for(j=1; j<=N; j++) {
if(A[i][j] == '0') jos[i][j] = jos[i+1][j] + 1;
}
}
for(i=1; i<=M; i++) {
for(j=1; j<=N; j++) {
if(A[i][j] == '0') st[i][j] = st[i][j-1] + 1;
}
}
for(i=1; i<=M; i++) {
for(j=N; j>=1; j--) {
if(A[i][j] == '0') dr[i][j] = dr[i][j+1] + 1;
}
}
for(i=1; i<=M; i++) {
int asmax = 0, hsmax = inf;
int ajmax = 0, hjmax = inf;
for(j=1; j<=N; j++) {
if(A[i][j] == '0') {
p = j; hsmax = inf; hjmax = inf;
while(p && A[i][p] == '0') {
hsmax = min(hsmax, sus[i][p]);
asmax = max(asmax, (j - p + 1)*hsmax);
hjmax = min(hjmax, jos[i][p]);
ajmax = max(ajmax, (j - p + 1)*hjmax);
p--;
}
}
}
linsus[i] = asmax;
linjos[i] = ajmax;
}
for(i=1; i<=N; i++) {
int asmax = 0, hsmax = inf;
int ajmax = 0, hjmax = inf;
for(j=1; j<=M; j++) {
if(A[j][i] == '0') {
p = j; hsmax = inf; hjmax = inf;
while(p && A[p][i] == '0') {
hsmax = min(hsmax, st[p][i]);
asmax = max(asmax, (j - p + 1)*hsmax);
hjmax = min(hjmax, dr[p][i]);
ajmax = max(ajmax, (j - p + 1)*hjmax);
p--;
}
}
}
colst[i] = asmax;
coldr[i] = ajmax;
}
int sol = 0;
for(i=1; i<=M; i++) {
for(j=i+1; j<=M; j++) {
sol = max(sol, linsus[i] + linjos[j]);
}
}
for(i=1; i<=N; i++) {
for(j=i+1; j<=N; j++) {
sol = max(sol, colst[i] + coldr[j]);
}
}
fprintf(f2, "%d\n", sol);
fclose(f1); fclose(f2);
return 0;
}