Pagini recente » Cod sursa (job #1487141) | Cod sursa (job #1576148) | Cod sursa (job #2860628) | Cod sursa (job #166745) | Cod sursa (job #501005)
Cod sursa(job #501005)
#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;
}