Pagini recente » Cod sursa (job #1005357) | Cod sursa (job #566193) | Cod sursa (job #1746461) | Cod sursa (job #1091593) | Cod sursa (job #3180030)
#include <fstream>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
struct rect {
int i1;
int j1;
int i2;
int j2;
};
int n, m;
bool matrix[201][201];
int lengths[201][201];
int taken[201][201];
rect firstRect;
int answer;
void initLengths() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (matrix[i][j] == 1)
lengths[i][j] = 0;
else
lengths[i][j] = lengths[i - 1][j] + 1;
}
}
}
bool isInRect(int i, int j, rect _rect) {
return i >= _rect.i1 && i <= _rect.i2 && j >= _rect.j1 && j <= _rect.j2;
}
void placeRect(rect _rect) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
taken[i][j] = taken[i][j - 1] + taken[i - 1][j] - taken[i - 1][j - 1];
if (isInRect(i, j, _rect)) {
taken[i][j]++;
}
}
}
}
int solve() {
int maxSize = 0;
for (int i2 = 1; i2 <= n; i2++) {
for (int i1 = 1; i1 <= i2; i1++) {
int start = 1;
int length = 0;
for (int j = 1; j <= m; j++) {
if (lengths[i2][j] == i2 - i1 + 1) {
length++;
}
else {
length = 0;
start = j + 1;
continue;
}
int alreadyTaken = taken[i2][j] - taken[i1 - 1][j] - taken[i2][start - 1] + taken[i1 - 1][start - 1];
if (maxSize < length * (i2 - i1 + 1) - alreadyTaken) {
maxSize = length * (i2 - i1 + 1) - alreadyTaken;
firstRect.i1 = i1;
firstRect.i2 = i2;
firstRect.j1 = start;
firstRect.j2 = j;
}
}
}
}
return maxSize;
}
int main()
{
char s;
fin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
fin >> s;
matrix[i][j] = s - '0';
}
}
initLengths();
answer += solve();
placeRect(firstRect);
answer += solve();
fout << answer;
}