Cod sursa(job #1962952)

Utilizator horiainfoTurcuman Horia horiainfo Data 12 aprilie 2017 10:24:33
Problema BMatrix Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.84 kb
/*
ID: Ionut
PROG: palsquare
LANG: C++11
*/

#include <fstream>
#include <algorithm>
#include <vector>

#define ll long long
#define N 100003
using namespace std;

ofstream fout("bmatrix.out");

struct Point {
	int x, y;

	Point(int x = 0, int y = 0) : x(x), y(y) {}
};

struct Rectangle {
	Point UpperLeft, LowerRight;
	int Area;

	Rectangle(int x1 = 0, int y1 = 0, int x2 = 0, int y2 = 0)
	{
		UpperLeft = Point(x1, y1);
		LowerRight = Point(x2, y2);
		RefreshArea();
	}

	Rectangle(Point upperLeft, Point lowerRight) : UpperLeft(upperLeft), LowerRight(lowerRight)
	{
		RefreshArea();
	}

	void RefreshArea()
	{
		Area = (LowerRight.x - UpperLeft.x + 1) * (LowerRight.y - UpperLeft.y + 1);
	}

	bool Contains(Point p)
	{
		return (p.x >= UpperLeft.x && p.x <= LowerRight.x) &&
			(p.y >= UpperLeft.y && p.y <= LowerRight.y);
	}

	bool Contains(Rectangle rect)
	{
		return Contains(rect.UpperLeft) && Contains(rect.LowerRight);
	}
};

int n, m, mat[202][202], maxArea;
vector<Rectangle> rectList;

char s[202];

int MaxAreaWithout(Rectangle rect1, Rectangle rect2)
{
	Rectangle r1 = Rectangle(rect1.UpperLeft, Point(rect1.LowerRight.x, rect2.UpperLeft.y - 1));
	Rectangle r2 = Rectangle(rect1.UpperLeft, Point(rect2.UpperLeft.x - 1, rect1.LowerRight.y));

	Rectangle r3 = Rectangle(Point(rect2.LowerRight.x + 1, rect1.UpperLeft.y), rect1.LowerRight);
	Rectangle r4 = Rectangle(Point(rect1.UpperLeft.x, rect2.LowerRight.y + 1), rect1.LowerRight);

	return max(r1.Area, max(r2.Area, max(r3.Area, r4.Area)));
}

Rectangle Intersection(Rectangle rect1, Rectangle rect2)
{
	if (rect1.Contains(rect2.UpperLeft))
	{
		Point lowerRight = Point(min(rect1.LowerRight.x, rect2.LowerRight.x),
								 min(rect1.LowerRight.y, rect2.LowerRight.y));

		return Rectangle(rect2.UpperLeft, lowerRight);
	}

	if (rect1.Contains(rect2.LowerRight))
	{
		Point upperLeft = Point(max(rect1.UpperLeft.x, rect2.UpperLeft.x), 
								max(rect1.UpperLeft.y, rect2.UpperLeft.y));

		return Rectangle(upperLeft, rect2.LowerRight);
	}

	Point upperRight = Point(rect2.UpperLeft.x, rect2.LowerRight.y);
	if (rect1.Contains(upperRight))
	{
		Point lowerLeft = Point(max(rect1.UpperLeft.x, rect2.UpperLeft.x),
								min(rect1.UpperLeft.y, rect2.UpperLeft.y));

		return Rectangle(upperRight.x, lowerLeft.y, lowerLeft.x, upperRight.y);
	}

	Point lowerLeft = Point(rect2.LowerRight.x, rect2.UpperLeft.y);
	if (rect1.Contains(lowerLeft))
	{
		Point upperRight = Point(min(rect1.UpperLeft.x, rect2.UpperLeft.x),
			max(rect1.UpperLeft.y, rect2.UpperLeft.y));

		return Rectangle(upperRight.x, lowerLeft.y, lowerLeft.x, upperRight.y);
	}

	Rectangle inters = Rectangle();
	inters.Area = 0;
	return inters;
}

int CalcArea(Rectangle rect1, Rectangle rect2)
{
	Rectangle inters = Intersection(rect1, rect2);

	if (inters.Area == 0)
		return rect1.Area + rect2.Area;

	int maxArea = rect1.Area + MaxAreaWithout(rect2, inters);
	return max(maxArea, rect2.Area + MaxAreaWithout(rect1, inters));
}

void Add(Rectangle rect)
{
	for (int i = 0; i < rectList.size(); i++)
		if (rectList[i].Contains(rect))
			return;

	for (int i = 0; i < rectList.size(); i++)
		maxArea = max(maxArea, CalcArea(rect, rectList[i]));
	rectList.push_back(rect);
}

int main()
{
	freopen("bmatrix.in", "r", stdin);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%s", &s);
		for (int j = 1; j <= m; j++)
			mat[i][j] = s[j - 1] - '0' + mat[i - 1][j];
	}
	
	for (int l1 = 1; l1 <= n; l1++)
		for (int l2 = n; l2 >= l1; l2--)
		{
			int lastC = 1;
			for (int j = 1; j <= m; j++)
				if (mat[l2][j] - mat[l1 - 1][j] != 0)
				{
					if (lastC < j)
						Add(Rectangle(lastC, l1, j - 1, l2));
					lastC = j + 1;
				}

			if (lastC <= m)
				Add(Rectangle(lastC, l1, m, l2));
		}

	fout << maxArea << '\n';
	return 0;
}