Pagini recente » Cod sursa (job #2080999) | Cod sursa (job #2478677) | Cod sursa (job #1667419) | Cod sursa (job #1358180) | Cod sursa (job #2941939)
#include <iostream>
#include <cstring>
#include <fstream>
#define MAX 202
using namespace std;
int n,m,a[MAX][MAX],v[MAX],dr[MAX],st[MAX],s[MAX],vf,ans;
char ch;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
void stersdrep(int x1, int y1, int x2, int y2){
for(int i = x1; i <= x2; i++){
for(int j = y1; j <= y2; j++){
a[i][j] = 1;
}
}
}
void getdrep(){
/// adauga la ans dreptunghiul de arie maxima si apoi il sterge
memset(v, 0, sizeof(v));
memset(dr, 0, sizeof(dr));
memset(st, 0, sizeof(st));
memset(s, 0, sizeof(s));
int maxi = 0, x = 0, y = 0, l1 = 0, l2 = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j] == 0){
v[j]++;
}else{
v[j] = 0;
}
}
vf = 0;
v[0] = -1;
s[vf] = 0;
for(int j = 1; j <= m; j++){
while(vf > 0 && v[j] <= v[s[vf]]){
vf--;
}
st[j] = s[vf]+1;
s[++vf] = j;
}
vf = 0;
v[m+1] = -1;
s[vf] = m+1;
for(int j = m; j >= 1; j--){
while(vf > 0 && v[j] <= v[s[vf]]){
vf--;
}
dr[j] = s[vf]-1;
s[++vf] = j;
}
for(int j = 1; j <= m; j++){
int arie = v[j]*(dr[j]-st[j]+1);
if(arie > maxi){
maxi = arie;
//cout << "(" << i << ", " << j << ") = " << arie << "; " << v[j] << "\n";
y = st[j];
x = i-v[j]+1;
l1 = v[j];
l2 = (dr[j]-st[j]+1);
}
}
}
//cout << maxi << "\n";
//cout << "(" << x << ", " << y << ", " << l1 << ", " << l2 << ")\n";
stersdrep(x, y, x+l1-1, y+l2-1);
/*for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cout << a[i][j] << " ";
}
cout << "\n";
}
cout << "\n";*/
ans += maxi;
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
fin >> ch;
a[i][j] = (ch-'0');
}
}
getdrep();
getdrep();
fout << ans;
return 0;
}