Code: Select all
#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef vector<bool> line;
typedef vector<line> matrix;
int size = 0;
istream& operator>>(istream& in, line& L)
{
string str;
int i;
in >> str;
size = str.size();
for(i = 0; i < size; ++i)
{
L[i] = (str[i] == '1');
}
return in;
}
int func(const matrix& m)
{
int i, j, p, k, columns, ret = 0, curr;
for(i = 0; i < size; ++i)
{
for(j = 0; j < size; ++j)
{
if(m[i][j] && ret < (size - i)*(size - j))
{
curr = 0;
p = i;
k = j;
columns = size;
for(p = i; p < size && m[p][j]; ++p)
{
for(k = j ; k < columns && m[p][k]; ++k);
if(k < columns)
{
columns = k;
}
curr = max(curr, (p - i + 1) * (k - j));
}
ret = max(curr, ret);
}
}
}
return ret;
}
int main()
{
int num, i;
matrix m(25);
for(i = 0; i < 25; ++i)
{
m[i].resize(25);
}
cin >> num;
while(num--)
{
cin >> m[0];
for(i = 1; i < size; ++i)
{
cin >> m[i];
}
cout << func(m) << (num == 0 ? "" : "\n\n");
}
return 0;
}
I start with cell with 1 and find the largest line with 1's - this is curr, size of line is columns
Then I start from the next line and find the largest line with ones with size <= columns (I am looking for rectangles), and curr = max(curr, size of new rect)
And so on, until the next line contains 1's.
But I get WA all times. Please notice that I have solved 108 - Maximum sums
