Pagini recente » Autentificare | Cod sursa (job #581102) | Cod sursa (job #1219755) | Cod sursa (job #2058859) | Cod sursa (job #749500)
Cod sursa(job #749500)
#include <fstream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
int N, M;
int overallMaxArea;
vector< vector<bool> > Matrix;
vector< vector<int> > Upper, Lower;
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()
{
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()
{
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>& leftToRight, bool direction)
{
stack< pair<int, int> > heights;
// go in the specified direction
for (int col = (direction? 0: M - 1); col != (direction? M: -1); col += (direction? 1: -1))
{
// remove larger values from stack
while (!heights.empty() && heights.top().first > columnSizes[col])
heights.pop();
// add current value if necessary
if (heights.empty() || !heights.empty() && heights.top().first < columnSizes[col])
{
heights.push(make_pair(columnSizes[col], col));
leftToRight[col] = col;
}
else
{
leftToRight[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 transpose(vector< vector<bool> >& Matrix, int& N, int &M)
{
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()
{
computeUpperColumns();
computeLowerColumns();
// go on rows of initial matrix
for (int row = 1; row < N; ++row)
{
int upperMaxArea = iterateAndComputeMaxArea(row - 1, Upper[row - 1]);
int lowerMaxArea = iterateAndComputeMaxArea(row, Lower[row]);
int totalMaxArea = upperMaxArea + lowerMaxArea;
overallMaxArea = totalMaxArea > overallMaxArea? totalMaxArea: overallMaxArea;
}
// forgot the transposed
transpose(Matrix, N, M);
computeUpperColumns();
computeLowerColumns();
// go on columns of initial matrix
for (int row = 1; row < N; ++row)
{
int upperMaxArea = iterateAndComputeMaxArea(row - 1, Upper[row - 1]);
int lowerMaxArea = iterateAndComputeMaxArea(row, Lower[row]);
int totalMaxArea = upperMaxArea + lowerMaxArea;
overallMaxArea = totalMaxArea > overallMaxArea? totalMaxArea: overallMaxArea;
}
}
void write()
{
ofstream fout("bmatrix.out");
fout << overallMaxArea;
fout.close();
}
int main()
{
read();
solve();
write();
}