Pagini recente » Cod sursa (job #478265) | Cod sursa (job #1828737) | Cod sursa (job #860024) | Cod sursa (job #2296294) | Cod sursa (job #1398619)
#include <fstream>
using namespace std;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
const int N = 205;
int st[N], tp = -1, m, n, z[N][N], sol;
char a[N][N];
void add(int x) {
st[++tp] = x;
}
void pop() {
--tp;
}
int main() {
fin >> m >> n;
fin.get();
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
fin >> a[i][j];
for (int k = 1; k < m; ++k) { //linie delimitatoare
int sol1 = 0, sol2 = 0;
for (int j = 1; j <= n; ++j)
z[k][j] = (a[k][j] == '0') ? (z[k - 1][j] + 1) : 0;
for (int j = 1; j <= n; ++j)
z[k + 1][j] = (a[k + 1][j] == '0');
for (int i = k + 2; i <= m; ++i)
for (int j = 1; j <= n; ++j)
z[i][j] = (a[i][j] == '0') ? (z[i - 1][j] + 1) : 0;
for (int i = 1; i <= m; ++i) {
tp = -1;
for (int j = 1; j <= n; ++j) {
if (tp != -1 && z[i][st[tp]] > z[i][j])
pop();
if (tp == -1 || z[i][st[tp]] < z[i][j])
add(j);
if (tp != -1) {
if (i <= k)
sol1 = max(sol1, (j - st[tp] + 1) * z[i][st[tp]]);
else
sol2 = max(sol2, (j - st[tp] + 1) * z[i][st[tp]]);
}
}
tp = -1;
for (int j = n; j; --j) {
if (tp != -1 && z[i][st[tp]] > z[i][j])
pop();
if (tp == -1 || z[i][st[tp]] < z[i][j])
add(j);
if (tp != -1) {
if (i <= k)
sol1 = max(sol1, (j - st[tp] + 1) * z[i][st[tp]]);
else
sol2 = max(sol2, (j - st[tp] + 1) * z[i][st[tp]]);
}
}
}
sol = max(sol, sol1 + sol2);
}
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
z[i][j] = (a[i][j] == '0') ? (z[i - 1][j] + 1) : 0;
for (int k = 1; k < n; ++k) {// coloana delimitatoare
int sol1 = 0, sol2 = 0;
for (int i = 1; i <= m; ++i) {
tp = -1;
for (int j = 1; j <= n; ++j) {
if (j == k + 1)
tp = -1;
if (tp != -1 && z[i][st[tp]] > z[i][j])
pop();
if (tp == -1 || z[i][st[tp]] < z[i][j])
add(j);
if (tp != -1) {
if (j <= k)
sol1 = max(sol1, (j - st[tp] + 1) * z[i][st[tp]]);
else
sol2 = max(sol2, (j - st[tp] + 1) * z[i][st[tp]]);
}
}
tp = -1;
for (int j = n; j; --j) {
if (j == k)
tp = -1;
if (tp != -1 && z[i][st[tp]] > z[i][j])
pop();
if (tp == -1 || z[i][st[tp]] < z[i][j])
add(j);
if (tp != -1) {
if (j <= k)
sol1 = max(sol1, (j - st[tp] + 1) * z[i][st[tp]]);
else
sol2 = max(sol2, (j - st[tp] + 1) * z[i][st[tp]]);
}
}
}
sol = max(sol, sol1 + sol2);
}
fout << sol;
}