Pagini recente » Cod sursa (job #1439217) | Cod sursa (job #1442138) | Cod sursa (job #385088) | Cod sursa (job #2908330) | Cod sursa (job #2799452)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int MAXN = 205;
char v[MAXN][MAXN];
// Numarul de elemente de '0' in fiecare directie
int Left[MAXN][MAXN], Right[MAXN][MAXN];
int Up[MAXN][MAXN], Down[MAXN][MAXN];
// Aria maxima a unui dreptunghi in cele 4 directii
int drUp[MAXN], drDown[MAXN];
int drRight[MAXN], drLeft[MAXN];
int Histogram(int n, int m, int H[]) {
int val[MAXN];
val[0] = val[n + 1] = -1; // Santinela
for(int i = 1; i <= n; i++)
val[i] = min(m, H[i]);
vector<int> L(MAXN);
stack<int> st; st.push(0);
for(int i = 1; i <= n; i++) {
while(val[st.top()] >= val[i])
st.pop();
L[i] = i - st.top();
st.push(i);
}
while(!st.empty()) st.pop();
st.push(n + 1);
vector<int> R(MAXN);
for(int i = n; i >= 1; i--) {
while(val[st.top()] >= val[i])
st.pop();
R[i] = st.top() - i;
st.push(i);
}
int ans = 0;
for(int i = 1; i <= n; i++)
ans = max(ans, val[i] * (R[i] + L[i] - 1));
return ans;
}
int main() {
int n, m, k;
fin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
fin >> v[i][j];
Up[i][j] = (v[i][j] == '0' ? Up[i - 1][j] + 1 : 0);
Left[j][i] = (v[i][j] == '0' ? Left[j - 1][i] + 1 : 0);
}
for(int i = n; i >= 1; i--)
for(int j = m; j >= 1; j--) {
Down[i][j] = (v[i][j] == '0' ? Down[i + 1][j] + 1 : 0);
Right[j][i] = (v[i][j] == '0' ? Right[j + 1][i] + 1 : 0);
}
for(int i = 1; i <= n; i++)
drUp[i] = max(drUp[i - 1], Histogram(m, i, Up[i]));
for(int j = 1; j <= m; j++)
drLeft[j] = max(drLeft[j - 1], Histogram(n, j, Left[j]));
for(int i = n; i >= 1; i--)
drDown[i] = max(drDown[i + 1], Histogram(m, n - i + 1, Down[i]));
for(int j = m; j >= 1; j--)
drRight[j] = max(drRight[j + 1], Histogram(n, m - j + 1, Right[j]));
int answer = 0;
for(int i = 1; i <= n; i++)
answer = max(answer, drUp[i] + drDown[i + 1]);
for(int j = 1; j <= m; j++)
answer = max(answer, drLeft[j] + drRight[j + 1]);
fout << answer << "\n";
return 0;
}