Cod sursa(job #749492)

Utilizator vlad.maneaVlad Manea vlad.manea Data 17 mai 2012 14:27:03
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.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));
	Upper.assign(N, vector<int>(M, 0));
	Lower.assign(N, vector<int>(M, 0));
	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()
{
	// 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()
{
	// 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 solve()
{
	computeUpperColumns();
	computeLowerColumns();

	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();
}