Cod sursa(job #1230762)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 19 septembrie 2014 11:13:26
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 3.12 kb
#include <fstream>
#include <vector>
#define INF 1000
#define pii pair<int, int>
using namespace std;
int T, n, m, sum[55][55], nr1;
char mat[55][55];
long long sol, total, put[55];
vector <pii> poz;

inline long long Cmmdc(long long a, long long b)
{
	long long r;
	while(b)
	{
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

inline void Solve()
{
	// momentan consider doar bounding-box-urile care sunt determinate de colturi '1'
	int i, j, nrint, xa, ya, xb, yb, arie;
	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= m; ++j)
		{
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i][j] - '0';
		}
	}
	total = put[nr1];
	sol = 1LL * nr1;
	// numar cazuri de genul
	// a1 si 1c
	// 1b si d1
	for(i = 0; i < nr1; ++i)
	{
		for(j = i + 1; j < nr1; ++j)
		{
			xa = min(poz[i].first, poz[j].first);
			xb = max(poz[i].first, poz[j].first);
			ya = min(poz[i].second, poz[j].second);
			yb = max(poz[i].second, poz[j].second);
			nrint = sum[xb][yb] - sum[xa - 1][yb] - sum[xb][ya - 1] + sum[xa - 1][ya - 1];
			arie = (xb - xa + 1) * (yb - ya + 1);
			sol += 1LL * arie * put[nrint - 2];
		}
	}
	// aici scad cazurile
	// 11
	// 11
	// pe care le-am pus in plus anterior
	for(i = 0; i < nr1; ++i)
	{
		for(j = i + 1; j < nr1; ++j)
		{
			xa = poz[i].first;
			ya = poz[i].second;
			xb = poz[j].first;
			yb = poz[j].second;
			if(mat[xa][yb] == '1' && mat[xb][ya] == '1')
			{
				xa = min(poz[i].first, poz[j].first);
				xb = max(poz[i].first, poz[j].first);
				ya = min(poz[i].second, poz[j].second);
				yb = max(poz[i].second, poz[j].second);
				nrint = sum[xb][yb] - sum[xa - 1][yb] - sum[xb][ya - 1] + sum[xa - 1][ya - 1];
				arie = (xb - xa + 1) * (yb - ya + 1);
				sol -= 1LL * arie * put[nrint - 4];
			}
		}
	}
}

inline void Back(int pas, int xa, int ya, int xb, int yb)
{
	if(pas == nr1)
	{
		if(xa == INF)
			return;
		sol += 1LL * (xb - xa + 1) * (yb - ya + 1);
		return;
	}
	Back(pas + 1, xa, ya, xb, yb);
	xa = min(xa, poz[pas].first);
	ya = min(ya, poz[pas].second);
	xb = max(xb, poz[pas].first);
	yb = max(yb, poz[pas].second);
	Back(pas + 1, xa, ya, xb, yb);
}

int main()
{
	int i, j;
	bool brut = true;
	long long C;
	put[0] = 1LL;
	for(i = 1; i < 55; ++i)
		put[i] = 2LL * put[i - 1];
	ifstream finb("boundingbox.in");
	finb >> T;
	while(T--)
	{
		nr1 = 0;
		finb >> n >> m;
		for(i = 1; i <= n; ++i)
		{
			finb >> (mat[i] + 1);
			for(j = 1; j <= m; ++j)
				nr1 += mat[i][j] - '0';
		}
		if(nr1 > 12)
			brut = false;
	}
	finb.close();
	
	ifstream fin("boundingbox.in");
	ofstream fout("boundingbox.out");
	fin >> T;
	while(T--)
	{
		nr1 = 0;
		poz.clear();
		fin >> n >> m;
		for(i = 1; i <= n; ++i)
		{
			fin >> (mat[i] + 1);
			for(j = 1; j <= m; ++j)
			{
				if(mat[i][j] == '1')
				{
					nr1++;
					poz.push_back(make_pair(i, j));
				}
			}
		}
		sol = 0LL;
		total = put[nr1];
		if(brut)
			Back(0, INF, INF, -INF, -INF);
		else
			Solve();
		C = Cmmdc(sol, total);
		sol /= C;
		total /= C;
		fout << sol << "/" << total << "\n";
	}
	fin.close();
	fout.close();
	return 0;
}