Cod sursa(job #749508)

Utilizator vlad.maneaVlad Manea vlad.manea Data 17 mai 2012 15:11:42
Problema BMatrix Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.95 kb
#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 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);

	computeUpperColumns();
	computeLowerColumns();

	// 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? maxRowArea: overallMaxArea;
	}
}

void write()
{
	ofstream fout("bmatrix.out");
	fout << overallMaxArea;
	fout.close();
}

int main()
{
	read();
	solve();
	trans();
	solve();
	write();
}