Pagini recente » Cod sursa (job #2686207) | Cod sursa (job #236716) | Cod sursa (job #168888) | Cod sursa (job #1234173) | Cod sursa (job #2929211)
#include <fstream>
#include <stack>
using namespace std;
ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");
const int NMAX = 2e2 + 10;
int n, m;
int a[NMAX + 1][NMAX + 1], b[NMAX + 1][NMAX + 1], h[NMAX + 1], last[NMAX + 1], st[NMAX + 1], dr[NMAX + 1];
struct dreptunghi{
int x1, y1, x2, y2;
};
void solve(int &amax, int lin, dreptunghi &d1, int a[][NMAX + 1]){
stack <int> s, d;
for(int i = 1; i <= n; i++){
while(!s.empty() && h[i] <= h[s.top()])
s.pop();
if(s.empty())
st[i] = 1;
else st[i] = s.top() + 1;
s.push(i);
}
for(int i = n; i >= 1; i--){
while(!d.empty() && h[i] <= h[d.top()])
d.pop();
if(d.empty())
dr[i] = n;
else dr[i] = d.top() - 1;
int arie = h[i] * (dr[i] - st[i] + 1);
if(amax < arie){
d1.x2 = lin;
d1.y2 = dr[i];
d1.x1 = lin - h[i] + 1;
d1.y1 = st[i];
amax = arie;
}
d.push(i);
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
char ch;
cin >> ch;
a[i][j] = ch - 48;
}
}
int amax = 0;
dreptunghi d1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j] == 1)
h[j] = 0;
else h[j] = 1 + last[j];
last[j] = h[j];
}
solve(amax, i, d1, a);
}
//cout << amax << " => (" << d1.x1 << ", " << d1.y1 << ") x (" << d1.x2 << ", " << d1.y2 << ")\n";
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(d1.x1 <= i && i <= d1.x2){
if(j < d1.y1)
b[i][j] = a[i][j];
else if(d1.y1 <= j && j <= d1.y2 && j + d1.y2 - d1.y1 + 1 <= m)
b[i][j] = a[i][j + d1.y2 - d1.y1 + 1];
else b[i][j] = 1;
}else
b[i][j] = a[i][j];
}
}
int amax2 = 0;
dreptunghi d2;
for(int i = 1; i <= m; i++)
last[i] = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(b[i][j] == 1)
h[j] = 0;
else h[j] = 1 + last[j];
last[j] = h[j];
}
solve(amax2, i, d2, b);
}
//cout << amax2 << " => (" << d2.x1 << ", " << d2.y1 << ") x (" << d2.x2 << ", " << d2.y2 << ")\n";
cout << amax + amax2;
return 0;
}