Cod sursa(job #749534)
#include <fstream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
int N, M;
int overallMaxArea;
vector< vector<bool> > Matrix;
void read()
{
string rowString;
ifstream fin("bmatrix.in");
fin >> N >> M;
Matrix.assign(N, vector<bool>(M, false));
rowString.assign(M + 1, 0);
// read matrix
for (int row = 0; row < N; ++row)
{
fin >> rowString;
for (int col = 0; col < M; ++col)
Matrix[row][col] = rowString.at(col) - '0';
}
fin.close();
}
void computeUpperColumns(vector< vector<int> >& Upper)
{
Upper.assign(N, vector<int>(M, 0));
// compute upper on first row
for (int col = 0; col < M; ++col)
Upper[0][col] = !Matrix[0][col];
// compute upper on next rows
for (int row = 1; row < N; ++row)
for (int col = 0; col < M; ++col)
Upper[row][col] = (!Matrix[row][col]) * (1 + Upper[row - 1][col]);
}
void computeLowerColumns(vector< vector<int> >& Lower)
{
Lower.assign(N, vector<int>(M, 0));
// compute lower on last row
for (int col = 0; col < M; ++col)
Lower[N - 1][col] = !Matrix[N - 1][col];
// compute lower on previous rows
for (int row = N - 2; row >= 0; --row)
for (int col = 0; col < M; ++col)
Lower[row][col] = (!Matrix[row][col]) * (1 + Lower[row + 1][col]);
}
void iterateAndComputeHeights(const vector<int>& columnSizes, vector<int>& heightsVector, bool direction)
{
stack< pair<int, int> > heights;
heights.push(make_pair(0, direction? 0: M - 1));
// go in the specified direction
for (int col = (direction? 0: M - 1); col != (direction? M: -1); col += (direction? 1: -1))
{
bool erased = false;
// remove larger values from stack
while (!heights.empty() && heights.top().first > columnSizes[col])
{
erased = true;
heightsVector[col] = heights.top().second;
heights.pop();
}
// add current value if necessary
if (heights.top().first < columnSizes[col])
{
heights.push(make_pair(columnSizes[col], col));
heightsVector[col] = erased? heightsVector[col]: col;
}
else
{
heightsVector[col] = heights.top().second;
}
}
}
int iterateAndComputeMaxArea(int row, const vector<int>& columnSizes)
{
vector<int> leftToRight(M, 0), rightToLeft(M, 0);
// iterate from left to right
iterateAndComputeHeights(columnSizes, leftToRight, true);
iterateAndComputeHeights(columnSizes, rightToLeft, false);
int maxArea = 0;
int nowArea;
for (int col = 0; col < M; ++col)
{
nowArea = (rightToLeft[col] - leftToRight[col] + 1) * columnSizes[col];
maxArea = nowArea > maxArea? nowArea: maxArea;
}
return maxArea;
}
void trans()
{
vector< vector<bool> > Transposed;
Transposed.assign(M, vector<bool>(N, 0));
for (int row = 0; row < N; ++row)
for (int col = 0; col < M; ++col)
Transposed[col][row] = Matrix[row][col];
Matrix.clear();
Matrix.assign(M, vector<bool>(N, 0));
N = N + M;
M = N - M;
N = N - M;
for (int row = 0; row < N; ++row)
for (int col = 0; col < M; ++col)
Matrix[row][col] = Transposed[row][col];
}
void solve()
{
vector<int> upperMaxAreas(N, 0), lowerMaxAreas(N, 0);
vector< vector<int> > Upper, Lower;
computeUpperColumns(Upper);
computeLowerColumns(Lower);
// go on rows of initial matrix
for (int row = 1; row < N; ++row)
{
upperMaxAreas[row - 1] = iterateAndComputeMaxArea(row - 1, Upper[row - 1]);
lowerMaxAreas[row] = iterateAndComputeMaxArea(row, Lower[row]);
}
// update maximum upper areas
for (int row = 1; row < N; ++row)
upperMaxAreas[row] = upperMaxAreas[row] > upperMaxAreas[row - 1]? upperMaxAreas[row]: upperMaxAreas[row - 1];
// update maximum lower areas
for (int row = N - 2; row >= 0; --row)
lowerMaxAreas[row] = lowerMaxAreas[row] > lowerMaxAreas[row + 1]? lowerMaxAreas[row]: lowerMaxAreas[row + 1];
// update maximum area
for (int row = 1; row < N; ++row)
{
int maxRowArea = upperMaxAreas[row - 1] + lowerMaxAreas[row];
overallMaxArea = maxRowArea > overallMaxArea && upperMaxAreas[row - 1] && lowerMaxAreas[row]? maxRowArea: overallMaxArea;
}
}
void write()
{
ofstream fout("bmatrix.out");
fout << overallMaxArea;
fout.close();
}
int main()
{
read();
solve();
trans();
solve();
write();
}