Pagini recente » Cod sursa (job #1825384) | Cod sursa (job #2112046) | Cod sursa (job #926688) | Cod sursa (job #2416081) | Cod sursa (job #2715750)
#include <fstream>
#include <string>
#include <stack>
using namespace std;
ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");
const int NMAX = 200;
int N, M;
string s[NMAX + 2];
int h[NMAX + 2];
int maxUp[NMAX + 2], maxDown[NMAX + 2], maxLeft[NMAX + 2], maxRight[NMAX + 2];
int Solve(int l) {
int maxArea = 0;
stack <int> st;
st.push(0);
for(int i = 1; i <= l + 1; i++) {
while((int)st.size() > 1 && h[i] <= h[st.top()]) {
int H = h[st.top()];
st.pop();
maxArea = max(maxArea, H * (i - st.top() - 1));
}
st.push(i);
}
return maxArea;
}
void ClearH(int l) {
for(int i = 1; i <= l; i++) {
h[i] = 0;
}
}
int main() {
cin >> N >> M;
for(int i = 1; i <= N; i++) {
cin >> s[i];
}
for(int i = 1; i <= N; i++) {
for(int j = 0; j < M; j++) {
if(s[i][j] == '1') {
h[j + 1] = 0;
} else {
h[j + 1]++;
}
}
if(i == 3)
i++, i--;
maxUp[i] = max(maxUp[i - 1], Solve(M));
}
ClearH(M);
for(int i = N; i >= 1; i--) {
for(int j = 0; j < M; j++) {
if(s[i][j] == '1') {
h[j + 1] = 0;
} else {
h[j + 1]++;
}
}
maxDown[i] = max(maxDown[i + 1], Solve(M));
}
ClearH(M);
for(int j = 1; j <= M; j++) {
for(int i = 1; i <= N; i++) {
if(s[i][j - 1] == '1') {
h[i] = 0;
} else {
h[i]++;
}
}
maxLeft[j] = max(maxLeft[j - 1], Solve(N));
}
ClearH(N);
for(int j = M; j >= 1; j--) {
for(int i = 1; i <= N; i++) {
if(s[i][j - 1] == '1') {
h[i] = 0;
} else {
h[i]++;
}
}
maxRight[j] = max(maxRight[j + 1], Solve(N));
}
int maxArea = 0;
for(int i = 1; i <= N; i++) {
maxArea = max(maxArea, maxUp[i] + maxDown[i + 1]);
}
for(int j = 1; j <= M; j++) {
maxArea = max(maxArea, maxLeft[j] + maxRight[j + 1]);
}
cout << maxArea << '\n';
return 0;
}