Cod sursa(job #1230806)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 19 septembrie 2014 11:45:04
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 5.71 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 int Sum(int xa, int ya, int xb, int yb)
{
	if(xa > xb || ya > yb)
		return 0;
	return (sum[xb][yb] - sum[xa - 1][yb] - sum[xb][ya - 1] + sum[xa - 1][ya - 1]);
}

inline void Solve()
{
	int i, j, nrint, xa, ya, xb, yb, arie, nr[4];
	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;
	// acum numar cazurile in care obligatoriu am macar doua coluturi '1' opuse
	// 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(xa, ya, xb, yb);
			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(xa = 1; xa <= n; ++xa)
	{
		for(ya = 1; ya <= m; ++ya)
		{
			for(xb = xa + 1; xb <= n; ++xb)
			{
				for(yb = ya + 1; yb <= m; ++yb)
				{
					if(mat[xa][ya] == '1' && mat[xb][yb] == '1' && mat[xa][yb] == '1' && mat[xb][ya] == '1')
					{
						nrint = Sum(xa, ya, xb, yb);
						arie = (xb - xa + 1) * (yb - ya + 1);
						sol -= 1LL * arie * put[nrint - 4];
					}
				}
			}
		}
	}
	// acum numar cazurile in care obligatoriu nu am niciun colt '1'
	for(xa = 1; xa <= n; ++xa)
	{
		for(ya = 1; ya <= m; ++ya)
		{
			for(xb = xa + 1; xb <= n; ++xb)
			{
				for(yb = ya + 1; yb <= m; ++yb)
				{
					nrint = Sum(xa, ya, xb, yb);
					nrint -= (mat[xa][ya] - '0' + mat[xa][yb] - '0' + mat[xb][ya] - '0' + mat[xb][yb] - '0');
					nr[0] = Sum(xa, ya + 1, xa, yb - 1);
					nr[1] = Sum(xa + 1, ya, xb - 1, ya);
					nr[2] = Sum(xb, ya + 1, xb, yb - 1);
					nr[3] = Sum(xa + 1, yb, xb - 1, yb);
					nrint -= (nr[0] + nr[1] + nr[2] + nr[3]);
					arie = (xb - xa + 1) * (yb - ya + 1);
					sol += 1LL * arie * put[nrint] * (put[nr[0]] - 1) * (put[nr[1]] - 1) * (put[nr[2]] - 1) * (put[nr[3]] - 1);
				}
			}
		}
	}
	// acum numar cazurile in care obligatoriu am macar un colt '1', fara a avea doua colturi opuse '1'
	for(xa = 1; xa <= n; ++xa)
	{
		for(ya = 1; ya <= m; ++ya)
		{
			for(xb = xa + 1; xb <= n; ++xb)
			{
				for(yb = ya + 1; yb <= m; ++yb)
				{
					nrint = Sum(xa, ya, xb, yb);
					nrint -= (mat[xa][ya] - '0' + mat[xa][yb] - '0' + mat[xb][ya] - '0' + mat[xb][yb] - '0');
					nr[0] = Sum(xa, ya + 1, xa, yb - 1); // linia xa
					nr[1] = Sum(xa + 1, ya, xb - 1, ya); // coloana ya
					nr[2] = Sum(xb, ya + 1, xb, yb - 1); // linia xb
					nr[3] = Sum(xa + 1, yb, xb - 1, yb); // coloana yb
					nrint -= (nr[0] + nr[1] + nr[2] + nr[3]);
					arie = (xb - xa + 1) * (yb - ya + 1);
					// cazul doua colturi alaturate si o latura
					if(mat[xa][ya] == '1')
					{
						if(mat[xa][yb] == '1')
							sol += 1LL * arie * put[nrint] * put[nr[0]] * put[nr[1]] * put[nr[3]] * (put[nr[2]] - 1);
						if(mat[xb][ya] == '1')
							sol += 1LL * arie * put[nrint] * put[nr[0]] * put[nr[1]] * put[nr[2]] * (put[nr[3]] - 1);
					}
					if(mat[xa][yb] == '1' && mat[xb][yb] == '1')
						sol += 1LL * arie * put[nrint] * put[nr[0]] * put[nr[2]] * put[nr[3]] * (put[nr[1]] - 1);
					if(mat[xb][ya] == '1' && mat[xb][yb] == '1')
						sol += 1LL * arie * put[nrint] * put[nr[1]] * put[nr[2]] * put[nr[3]] * (put[nr[0]] - 1);
					// cazul cu un colt si doua laturi
					if(mat[xa][ya] == '1')
						sol += 1LL * arie * put[nrint] * put[nr[0]] * put[nr[1]] * (put[nr[2]] - 1) * (put[nr[3]] - 1);
					if(mat[xa][yb] == '1')
						sol += 1LL * arie * put[nrint] * put[nr[0]] * put[nr[3]] * (put[nr[1]] - 1) * (put[nr[2]] - 1);
					if(mat[xb][ya] == '1')
						sol += 1LL * arie * put[nrint] * put[nr[1]] * put[nr[2]] * (put[nr[0]] - 1) * (put[nr[3]] - 1);
					if(mat[xb][yb] == '1')
						sol += 1LL * arie * put[nrint] * put[nr[2]] * put[nr[3]] * (put[nr[0]] - 1) * (put[nr[1]] - 1);
				}
			}
		}
	}
	
}

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