Pagini recente » Cod sursa (job #2553959) | Cod sursa (job #2877587) | Cod sursa (job #555395) | Cod sursa (job #535187) | Cod sursa (job #1398595)
#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 i = 1; i <= k; ++i)
for (int j = 1; j <= n; ++j)
z[i][j] = (a[i][j] == '0') ? (z[i - 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;
/*fout << k << "===\n";
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j)
fout << z[i][j] << " ";
if (i == k)
fout << "\n";
fout << "\n";
}
fout << "\n";*/
for (int i = 1; i <= k; ++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)
sol1 = max(sol1, (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)
sol1 = max(sol1, (j - st[tp] + 1) * z[i][st[tp]]);
}
}
for (int i = k + 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)
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)
sol2 = max(sol2, (j - st[tp] + 1) * z[i][st[tp]]);
}
}
sol = max(sol, sol1 + sol2);
//fout << "linia " << k << " " << sol1 << " " << sol2 << "\n";
}
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 <= k; ++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)
sol1 = max(sol1, (j - st[tp] + 1) * z[i][st[tp]]);
}
tp = -1;
for (int j = k; 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)
sol1 = max(sol1, (j - st[tp] + 1) * z[i][st[tp]]);
}
tp = -1;
for (int j = k + 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)
sol2 = max(sol2, (j - st[tp] + 1) * z[i][st[tp]]);
}
tp = -1;
for (int j = n; j != k; --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)
sol2 = max(sol2, (j - st[tp] + 1) * z[i][st[tp]]);
}
}
sol = max(sol, sol1 + sol2);
}
fout << sol;
}